×
Allender, Eric; Jiao, Jia

Depth reduction for noncommutative arithmetic circuits. (English) Zbl 1310.68097

Proceedings of the 25th annual ACM symposium on theory of computing, STOC ’93. San Diego, CA, USA, May 16–18, 1993. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-591-7). 515-522 (1993).
For the entire collection see [Zbl 1285.68003].

Cited in 9 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Cite Review PDF
Full Text: DOI

References:

[1] L. Adleman, Two theorems on random polynomial time Proc. 19th FOCS (1978) pp. 75- 83.
[2] E. Allender, A note on the power of threshold circuits, Proc. 30th FOCS, pp. 580-584. 10.1109/SFCS.1989.63538
[3] E. Allender, D. Bruschi, and G. Pighizzini, The complexity of computing mazimal word functions, DIMACS tech report 92-15.
[4] E. Allender and U. Hertrampf, On the power of uniform families of constant depth threshold circuits, Proc. 15th MFCS, 1990, Lecture Notes in Computer Science 452, pp. 158- 164. · Zbl 0732.94018
[5] E. Allender and U. Hertrampf, Depth reduction for circuits of unbounded fan-in, to appear in Information and Computation. Preliminary versions appeared as {A189, Att90} 10.1006/inco.1994.1057
[6] C. /#lvarez and B. Jenner, A note on log space optimization, report, L.S.I., Universitat Polit#cnica Catalunya, Barcelona, 1992.
[7] C./klvarez and B. Jenner, A very hard log. space counting class, Theoretical Computer Science 107 (1993) 3-30. 10.1016/0304-3975(93)90252-O · Zbl 0813.68098
[8] P.W. Beame, S. A. Cook, and H. J. Hoover, Log depth circuits for division and related problems, SIAM J. Comput. 15 (1986) 994- 1003. 10.1137/0215070 · Zbl 0619.68047
[9] R. Beigel and J. Tarui, On A CC, Proe. 32nd FOCS (1991) 783-792. 10.1109/SFCS.1991.185449
[10] J. Boyar, G. Frandsen, and G. Sturtivant, An arithmetical model of computation equivalent to threshold circuits, Theoretical Computer Science 93 (1992) 303-319. 10.1016/0304-3975(92)90335-D · Zbl 0745.68043
[11] S. Cook, Characterization of pushdown machines in terms of time-bounded computers, J. ACM 18 (1971) 4-18. 10.1145/321623.321625 · Zbl 0222.02035
[12] C. Damm, L=L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt- Universitht zu Berlin, 1991.
[13] B. Jenner, personal communication.
[14] M. jerrum and M. Snir, Some ezact eomplezity results for straight.line computations over semirings, J. ACM 29 (1982) 874-897. 10.1145/322326.322341 · Zbl 0485.68038
[15] It. Kannan, H. Venkateswaran, V. Vinay, and A. Yao, A circuit.based proof of Toda’s theorem, to appear in Information and Computation. 10.1006/inco.1993.1033
[16] S. It. Kosaraju, On the parallel evaluation of classes of circuits, Proc. 10th FST&TCS, Lecture Notes in Computer Science 472 (1990) 232-237. · Zbl 0733.68040
[17] M. Krentel, The eomplezity of optimization problems, JCSS 36 (1988) 490-509. 10.1016/0022-0000(88)90039-6 · Zbl 0652.68040
[18] G. Miller, V. Itamachandran, and E. Kaltofen, E#cient parallel evaluation of straight-line code and arithmetic circuits, SIAM J. Comput. 17 (1988) 687-695. 10.1137/0217044 · Zbl 0651.68044
[19] G. Miller and S.-H. Teng, Dynamic parallel complexity of computational circuits, Proc. 19th STOC (1987) 478-489. 10.1145/28395.28423
[20] N. Nisan, Lower bounds for non-commutative computation, Proc. 23rd STOC (1991) 410-418. 10.1145/103418.103462
[21] J. Iteif and S. ’rate, On threshold circuits and polynomial computation, SIAM j. Comput. 21 (1992) 896-908. 10.1137/0221053 · Zbl 0765.68057
[22] S. Toda, PP is as hard as the polynomialtime hierarchy SIAM J. Comput. 20 (1991) 865-877. 10.1137/0220053 · Zbl 0733.68034
[23] S. Toda, Counting problems computationally equivalent to the determinant, manuscript.
[24] S. Toda, Classes of arithmetic circuits capturing the complezity of computing the determinant, IEICE Trans. Inf. and Syst., vol. E75-D (1992) 116-124.
[25] L. Valiant, Completeness classes in algebra, Proe. l lth STOC (1979) 249-261. 10.1145/800135.804419
[26] L. Valiant, Why is Boolean complexity theory difficult? in Boolean Function Complezi#y, edited by M. S. Paterson, London Mathematical Society Lecture Notes Series 169, Cambridge University Press, 1992.
[27] L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, Fast parallel computation of poly. nomials using few processors, SIAM j. Cornput. 12 (1983)641-644. · Zbl 0524.68028
[28] L. Valiant and V. Vazirani, V, NP is as easy as detecting unique solutions Theoretlcal Computer Science 47 (1986) 85-93. · Zbl 0621.68030
[29] H. Venkateswaran, Properties tttat characterize I, OGCFI,, JCSS 42 (1991) 380-404. 10.1016/0022-0000(91)90020-6
[30] H. Venk#teswaran, Circuit definitions of nondeterministic complezity classes, SIAM J. Comput. 21 (1992) 655-670. 10.1137/0221040 · Zbl 0749.68039
[31] H. Venk#teswaran and M. Tompa, A new pebble game float characterizes parallel com. plezity classes, SIAM j. Comput. 18 (1989) 533-549. 10.1137/0218036 · Zbl 0678.68047
[32] V. Vinay, Countin9 auziliary pushdown au. tomata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference (1991) 270-284.
[33] V. Vinay, Semi’unboundedness and complez. ity classes, doctoral dissertation, Indian Institute of Science, Bangalore.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.