Threshold circuits for iterated matrix product and powering

Carlo Mereghetti; Beatrice Palano

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

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

How to cite

top

Mereghetti, Carlo, and Palano, Beatrice. "Threshold circuits for iterated matrix product and powering." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 34.1 (2000): 39-46. <http://eudml.org/doc/92622>.

@article{Mereghetti2000,
author = {Mereghetti, Carlo, Palano, Beatrice},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {complexity of computing},
language = {eng},
number = {1},
pages = {39-46},
publisher = {EDP-Sciences},
title = {Threshold circuits for iterated matrix product and powering},
url = {http://eudml.org/doc/92622},
volume = {34},
year = {2000},
}

TY - JOUR
AU - Mereghetti, Carlo
AU - Palano, Beatrice
TI - Threshold circuits for iterated matrix product and powering
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2000
PB - EDP-Sciences
VL - 34
IS - 1
SP - 39
EP - 46
LA - eng
KW - complexity of computing
UR - http://eudml.org/doc/92622
ER -

References

top
  1. [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. Zbl0757.68057MR1163944
  2. [2] S. A. Cook, A taxonomy of problems with fast parallel algorithms. Inform. and Control. 64 (1985) 2-22. Zbl0575.68045MR837088
  3. [3] L. E. Dickson, Linear Groups with an Exposition of the Galois Field Theory. 1901. Reprinted by Dover (1958). Zbl0082.24901MR104735JFM32.0128.01
  4. [4] S. Eilenberg, Automata, Languages, and Machines. Academic Press (1976). Zbl0359.94067
  5. [5] W. Eberly, Very fast parallel polynomial arithmetic. SIAM J. Comput. 18 (1989) 955-976. Zbl0694.68029MR1015268
  6. [6] F. Gécseg, Products of Automata. Springer Verlag, Monogr. Theoret. Comput. Sci. EATCS Ser. 7 (1986). Zbl0622.68049MR882544
  7. [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 7 . Comp. System Sci. 46 (1993) 129-154. Zbl0801.68052MR1217153
  8. [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. Zbl0835.68041
  9. [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. MR1700322
  10. [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 http://gongolo.usr.dsi.unimi.it/~mereghc/papers/TR_242-99.ps Zbl1020.68057
  11. [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 http://gongolo.usr.dsi.unimi.it/~mereghc/papers/TR_245-00.ps Zbl0962.68089
  12. [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. Zbl0835.68099
  13. [13] G. Shilov, Linear Algebra. Prentice Hall (1971). Reprinted by Dover (1977). Zbl0218.15003MR276252
  14. [14] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser (1994). Zbl0816.68086MR1269544
  15. [15] I. Wegener, The Complexity of Boolean Functions. Teubner (1987). Zbl0623.94018MR905473
  16. [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. Zbl0770.68076MR1219848

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.