Threshold Circuits for Iterated Matrix Product and Powering

Carlo Mereghetti; Beatrice Palano

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 1, page 39-46
  • ISSN: 0988-3754

Abstract

top
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension k × k matrices with integer or rational entries is studied. We call these two problems 𝖨𝖬𝖯 𝗄 and 𝖬𝖯𝖮𝖶 𝗄 , respectively, for short. We prove that: (i) For k ≥ 2 , 𝖨𝖬𝖯 𝗄 does not belong to TC 0 , unless TC 0 = NC 1 .newline (ii) For stochastic matrices : 𝖨𝖬𝖯 2 belongs to TC 0 while, for k ≥ 3 , 𝖨𝖬𝖯 𝗄 does not belong to TC 0 , unless TC 0 = NC 1 . (iii) For any k, 𝖬𝖯𝖮𝖶 𝗄 belongs to TC 0 .

How to cite

top

Mereghetti, Carlo, and Palano, Beatrice. "Threshold Circuits for Iterated Matrix Product and Powering." RAIRO - Theoretical Informatics and Applications 34.1 (2010): 39-46. <http://eudml.org/doc/222041>.

@article{Mereghetti2010,
abstract = { The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems $\sf IMP_k$ and $\sf MPOW_k$, respectively, for short. We prove that: (i) For $k\geq2$, $\sf IMP_k$ does not belong to $\{\rm TC\}^0$, unless $\{\rm TC\}^0=\{\rm NC\}^1$.newline (ii) For stochastic matrices : $\sf IMP_2$ belongs to $\{\rm TC\}^0$ while, for $k\geq3$, $\sf IMP_k$ does not belong to $\{\rm TC\}^0$, unless $\{\rm TC\}^0=\{\rm NC\}^1$. (iii) For any k, $\sf MPOW_k$ belongs to $\{\rm TC\}^0$. },
author = {Mereghetti, Carlo, Palano, Beatrice},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Threshold circuits; iterated matrix product; matrix powering.; complexity of computing},
language = {eng},
month = {3},
number = {1},
pages = {39-46},
publisher = {EDP Sciences},
title = {Threshold Circuits for Iterated Matrix Product and Powering},
url = {http://eudml.org/doc/222041},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Mereghetti, Carlo
AU - Palano, Beatrice
TI - Threshold Circuits for Iterated Matrix Product and Powering
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 1
SP - 39
EP - 46
AB - The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems $\sf IMP_k$ and $\sf MPOW_k$, respectively, for short. We prove that: (i) For $k\geq2$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$.newline (ii) For stochastic matrices : $\sf IMP_2$ belongs to ${\rm TC}^0$ while, for $k\geq3$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$. (iii) For any k, $\sf MPOW_k$ belongs to ${\rm TC}^0$.
LA - eng
KW - Threshold circuits; iterated matrix product; matrix powering.; complexity of computing
UR - http://eudml.org/doc/222041
ER -

References

top
  1. D.A. Mix Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1. J. Comp. System Sci.44 (1992) 478-499.  
  2. S.A. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control.64 (1985) 2-22.  
  3. L.E. Dickson, Linear Groups with an Exposition of the Galois Field Theory. 1901. Reprinted by Dover (1958).  
  4. S. Eilenberg, Automata, Languages, and Machines. Academic Press (1976).  
  5. W. Eberly, Very fast parallel polynomial arithmetic. SIAM J. Comput.18 (1989) 955-976.  
  6. F. Gécseg, Products of Automata. Springer Verlag, Monogr. Theoret. Comput. Sci. EATCS Ser. 7 (1986).  
  7. A. Hajnal, W. Maaß, P. Pudlák, M. Szegedy and G. Turán, Threshold circuits of bounded depth, in Proc. 28th IEEE Symposium on Foundations of Computer Science (1987) 99-110. Also in J. Comp. System Sci. 46 (1993) 129-154.  
  8. T. Hofmeister, Depth-efficient threshold circuits for arithmetic functions, edited by V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Theoretical Advances in Neural Computation and Learning. Kluwer Academic (1994) 37-84.  
  9. C. Mereghetti and B. Palano, Threshold circuits for some matrix operations. Consequences on regular and probabilistic languages. Theoretical Computer Science - Proceedings of the 6th Italian Conference. World Scientific (1998) 216-227.  
  10. C. Mereghetti and B. Palano, The Parallel Complexity of Deterministic and Probabilistic Automata. Technical Report No. 242-99, Dipartimento di Scienze dell'Informazione. Università degli Studi di Milano (1999). Available at  URIhttp://gongolo.usr.dsi.unimi.it/mereghc/papers/TR_242-99.ps
  11. C. Mereghetti and B. Palano, Matrix Powering in Constant Depth. Technical Report No. 245-00, Dipartimento di Scienze dell'Informazione. Università degli Studi di Milano (2000). Available at  URIhttp://gongolo.usr.dsi.unimi.it/mereghc/papers/TR_245-00.ps
  12. V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Neural models and spectral methods, edited by V. Roychowdhury, K.-Y. Siu and A. Orlitsky, Theoretical Advances in Neural Computation and Learning. Kluwer Academic (1994) 3-36.  
  13. G. Shilov, Linear Algebra. Prentice Hall (1971). Reprinted by Dover (1977).  
  14. H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser (1994).  
  15. I. Wegener, The Complexity of Boolean Functions. Teubner (1987).  
  16. I. Wegener, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions. Inform. Process. Lett.46 (1993) 85-87.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.