# 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

## Access Full Article

top## Abstract

top## How to cite

topMereghetti, 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- D.A. Mix Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1. J. Comp. System Sci.44 (1992) 478-499. Zbl0757.68057
- S.A. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control.64 (1985) 2-22. Zbl0575.68045
- L.E. Dickson, Linear Groups with an Exposition of the Galois Field Theory. 1901. Reprinted by Dover (1958). Zbl32.0128.01
- S. Eilenberg, Automata, Languages, and Machines. Academic Press (1976).
- W. Eberly, Very fast parallel polynomial arithmetic. SIAM J. Comput.18 (1989) 955-976. Zbl0694.68029
- F. Gécseg, Products of Automata. Springer Verlag, Monogr. Theoret. Comput. Sci. EATCS Ser. 7 (1986). Zbl0622.68049
- 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. Zbl0801.68052
- 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. Zbl0835.68041
- 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.
- 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 Zbl1020.68057URIhttp://gongolo.usr.dsi.unimi.it/mereghc/papers/TR_242-99.ps
- 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 Zbl0962.68089URIhttp://gongolo.usr.dsi.unimi.it/mereghc/papers/TR_245-00.ps
- 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. Zbl0835.68099
- G. Shilov, Linear Algebra. Prentice Hall (1971). Reprinted by Dover (1977). Zbl0218.15003
- H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser (1994). Zbl0816.68086
- I. Wegener, The Complexity of Boolean Functions. Teubner (1987). Zbl0623.94018
- I. Wegener, Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions. Inform. Process. Lett.46 (1993) 85-87. Zbl0770.68076

## NotesEmbed ?

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