{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:27Z","timestamp":1742617227971,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":109,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620341"},{"type":"electronic","value":"9783540496311"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-62034-6_33","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:31:27Z","timestamp":1330295487000},"page":"1-18","source":"Crossref","is-referenced-by-count":13,"title":["Circuit complexity before the dawn of the new millennium"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"M. Agrawal and E. Allender. An isomorphism theorem for circuit complexity. In IEEE Conference on Computational Complexity, pages 2\u201311, 1996.","key":"1_CR1","DOI":"10.1109\/CCC.1996.507663"},{"unstructured":"M. Agrawal, E. Allender, and S. Rudich. Reductions in circuit complexity: An isomorphism theorem and a gap theorem. submitted; preliminary version appeared as [AA96].","key":"1_CR2"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF01215346","volume":"14","author":"J. Aspnes","year":"1994","unstructured":"J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The expressive power of voting polynomials. Combinatorica, 14:135\u2013148, 1994.","journal-title":"Combinatorica"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0020-0190(91)90015-A","volume":"40","author":"E. Allender","year":"1991","unstructured":"E. Allender and V. Gore. Rudimentary reductions revisited. Information Processing Letters, 40:89\u201395, 1991.","journal-title":"Information Processing Letters"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1137\/S0097539792233907","volume":"23","author":"E. Allender","year":"1994","unstructured":"E. Allender and V. Gore. A uniform circuit lower bound for the permanent. SIAM Journal on Computing, 23:1026\u20131049, 1994.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1006\/inco.1994.1057","volume":"112","author":"E. Allender","year":"1994","unstructured":"E. Allender and U. Hertrampf. Depth reductions for circuits of unbounded fan-in. Information and Computation, 112:217\u2013238, 1994.","journal-title":"Information and Computation"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u03c3 1 1 -formulae on finite structures. Annals of Pure and Applied Logic, 24:1\u201348, 1983.","journal-title":"Annals of Pure and Applied Logic"},{"unstructured":"E. Allender. The permanent requires large uniform threshold circuits. Submitted. A preliminary version of this paper appeared as [All96].","key":"1_CR8"},{"doi-asserted-by":"crossref","unstructured":"E. Allender. A note on uniform circuit lower bounds for the counting hierarchy. In International Conference on Computing and Combinatorics Conference (COCOON), volume 1090 of Lecture Notes in Computer Science, pages 127\u2013135. Springer-Verlag, 1996.","key":"1_CR9","DOI":"10.1007\/3-540-61332-3_145"},{"doi-asserted-by":"crossref","unstructured":"E. Allender and M. Strauss. Measure on small complexity classes, with applications for BPP. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 807\u2013818, 1994.","key":"1_CR10","DOI":"10.1109\/SFCS.1994.365713"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"D. A. Mix Barrington. Quasipolynomial size circuit classes. In IEEE Structure in Complexity Theory Conference, pages 86\u201393, 1992.","key":"1_CR12","DOI":"10.1109\/SCT.1992.215383"},{"key":"1_CR13","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01263424","volume":"4","author":"D. A. Mix Barrington","year":"1994","unstructured":"D. A. Mix Barrington, R. Beigel, and S. Rudich. Representing Boolean functions as polynomials modulo composite numbers. Computational Complexity, 4:367\u2013382, 1994.","journal-title":"Computational Complexity"},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0020-0190(89)90052-5","volume":"32","author":"D. A. Mix Barrington","year":"1989","unstructured":"D. A. Mix Barrington and J. Corbett. On the relative complexity of some languages in NC1. Information Processing Letters, 32:251\u2013256, 1989.","journal-title":"Information Processing Letters"},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/0304-3975(91)90357-8","volume":"78","author":"D. A. Mix Barrington","year":"1991","unstructured":"D. A. Mix Barrington and J. Corbett. A note on some languages in uniform ACC0. Theoretical Computer Science, 78:357\u2013362, 1991.","journal-title":"Theoretical Computer Science"},{"unstructured":"P. Beame. A switching lemma primer. manuscript, available from http:\/\/www.cs.washington.edu\/homes\/beame\/papers.html.","key":"1_CR16"},{"doi-asserted-by":"crossref","unstructured":"R. Beigel. The polynomial method in circuit complexity. In IEEE Structure in Complexity Theory Conference, pages 82\u201395, 1993.","key":"1_CR17","DOI":"10.1109\/SCT.1993.336538"},{"key":"1_CR18","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/BF01263420","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel. When do extra majority gates help? polylog(n) majority gates are equivalent to one. Computational Complexity, 4:314\u2013324, 1994.","journal-title":"Computational Complexity"},{"unstructured":"H. Buhrman and L. Fortnow. Personal Communication, Dagstuhl workshop on Structure and Complexity, 1996.","key":"1_CR19"},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307\u2013318, 1993.","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"H. Buhrman and S. Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Foundations of Software Technology and Theoretical Computer Science (FST&TCS), volume 652 of Lecture Notes in Computer Science, pages 116\u2013127. Springer-Verlag, 1992.","key":"1_CR21","DOI":"10.1007\/3-540-56287-7_99"},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. Mix Barrington","year":"1990","unstructured":"D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser. The complexity of finite functions. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science (Vol. A: Algorithms and Complexity). Elsevier and MIT Press, 1990.","key":"1_CR23","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01263421","volume":"4","author":"D. A. Mix Barrington","year":"1994","unstructured":"D. A. Mix Barrington and H. Straubing. Complex polynomials and circuit lower bounds for modular counting. Computational Complexity, 4:325\u2013338, 1994.","journal-title":"Computational Complexity"},{"key":"1_CR25","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1006\/jcss.1995.1029","volume":"50","author":"D. A. Mix Barrington","year":"1995","unstructured":"D. A. Mix Barrington and H. Straubing. Superlinear lower bounds for bounded-width branching programs. Journal of Computer and System Sciences, 50:374\u2013381, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D. A. Mix Barrington","year":"1990","unstructured":"D. A. Mix Barrington, H. Straubing, and D. Th\u00e9rien. Non-uniform automata over groups. Information and Computation, 89:109\u2013132, 1990.","journal-title":"Information and Computation"},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. Mix Barrington","year":"1988","unstructured":"D. A. Mix Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. Journal of the ACM, 35:941\u2013952, 1988.","journal-title":"Journal of the ACM"},{"key":"1_CR28","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel and J. Tarui. On ACC. Computational Complexity, 4:350\u2013367, 1994.","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"R. Beigel, J. Tarui, and S. Toda. On probabilistic ACC circuits with an exact-threshold output gate. In Proceedings of the 3rd ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation (ISAAC), volume 650 of Lecture Notes in Computer Science, pages 420\u2013429. Springer-Verlag, 1992.","key":"1_CR29","DOI":"10.1007\/3-540-56279-6_94"},{"doi-asserted-by":"crossref","unstructured":"S. Buss. Algorithm for Boolean formula evaluation and for tree contraction. In P. Clote and J. Kraj\u00ed\u010dek, editors, Arithmetic, Proof Theory, and Computational Complexity, volume 25 of Oxford Logic Guides, pages 96\u2013115. Clarendon Press, 1993.","key":"1_CR30","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"key":"1_CR31","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","volume":"38","author":"J. Cai","year":"1989","unstructured":"J. Cai. With probability 1, a random oracle separates PSPACE from the polynomial-time hierarchy. J. Computer and System Science, 38:68\u201385, 1989.","journal-title":"J. Computer and System Science"},{"unstructured":"H. Caussinus. A note on a theorem of Barrington, Straubing, and Th\u00e9rien. To appear in Information Processing Letters.","key":"1_CR32"},{"unstructured":"H. Caussinus. Contributions \u00e0 l'Etude du Non-d\u00e9terminisme Restreint. PhD thesis, Universit\u00e9 de Montr\u00e9al, 1996.","key":"1_CR33"},{"key":"1_CR34","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28:114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"H. Caussinus, P. McKenzie, D. Th\u00e9rien, and H. Vollmer. Nondeterministic NC1 computation. In Proceedings, 11th Annual IEEE Conference on Computational Complexity, pages 12\u201321, 1996.","key":"1_CR35","DOI":"10.1109\/CCC.1996.507664"},{"doi-asserted-by":"crossref","unstructured":"S. Chaudhuri and J. Radhakrishnan. Deterministic restrictions in circuit complexity. In ACM Symposium on Theory of Computing (STOC), pages 30\u201336, 1996.","key":"1_CR36","DOI":"10.1145\/237814.237824"},{"unstructured":"J.-Y. Cai, D. Sivakumar, and M. Strauss. Constant-depth circuits and the Lutz hypothesis. Manuscript.","key":"1_CR37"},{"key":"1_CR38","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13:423\u2013439, 1984.","journal-title":"SIAM Journal on Computing"},{"unstructured":"P. Enflo and M. Sitharam. Stable basis families and complexity lower bounds. Submitted.","key":"1_CR39"},{"doi-asserted-by":"crossref","unstructured":"K. Etessami. Counting quantifiers, successor relations, and logarithmic space. To appear in Journal of Computer and System Sciences. Preliminary version appeared in IEEE Structure in Complexity Theory Conference, 1995, pp. 2\u201311.","key":"1_CR40","DOI":"10.1109\/SCT.1995.514723"},{"key":"1_CR41","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1006\/inco.1995.1161","volume":"123","author":"L. Fortnow","year":"1995","unstructured":"L. Fortnow and S. Laplante. Circuit lower bounds \u00e0 la Kolmogorov. Information and Computation, 123:121\u2013126, 1995.","journal-title":"Information and Computation"},{"key":"1_CR42","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13\u201327, 1984.","journal-title":"Mathematical Systems Theory"},{"key":"1_CR43","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldmann","year":"1992","unstructured":"M. Goldmann, J. H\u00e5stad, and A. A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277\u2013300, 1992.","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"M. Goldmann and M. Karpinski. Simulating threshold circuits by majority circuits. In ACM Symposium on Theory of Computing (STOC), pages 551\u2013560, 1993.","key":"1_CR44","DOI":"10.1145\/167088.167234"},{"key":"1_CR45","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1006\/jcss.1995.1036","volume":"50","author":"F. Green","year":"1995","unstructured":"F. Green, J. K\u00f6bler, K. Regan, T. Schwentick, and J. Tor\u00e1n. The power of the middle bit of a #P function. Journal of Computer and System Sciences, 50:456\u2013467, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR46","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0020-0190(94)00221-J","volume":"53","author":"M. Goldmann","year":"1995","unstructured":"M. Goldmann. A note on the power of majority gates and modular gates. Information Processing Letters, 53:321\u2013327, 1995.","journal-title":"Information Processing Letters"},{"unstructured":"F. Green. Complex Fourier technique for lower bounds on the Mod-m degree. Submitted. An earlier version appeared as [Gre95].","key":"1_CR47"},{"doi-asserted-by":"crossref","unstructured":"F. Green. Lower bounds for depth-three circuits with equals and modgates. In Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 900 of Lecture Notes in Computer Science, pages 71\u201382. Springer-Verlag, 1995.","key":"1_CR48","DOI":"10.1007\/3-540-59042-0_63"},{"doi-asserted-by":"crossref","unstructured":"V. Grolmusz. A weight-size trade-off for circuits with MOD m gates. In ACM Symposium on Theory of Computing (STOC), 1994.","key":"1_CR49","DOI":"10.1145\/195058.195108"},{"key":"1_CR50","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1006\/jcss.1995.1069","volume":"51","author":"V. Grolmusz","year":"1995","unstructured":"V. Grolmusz. Separating the communication complexities of MOD m and MOD p circuits. Journal of Computer and System Sciences, 51:307\u2013313, 1995.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Vince Grolmusz. On the weak mod m representation of Boolean functions. Chicago Journal of Theoretical Computer Science, 1995(2), July 1995.","key":"1_CR51"},{"key":"1_CR52","volume-title":"Computational Limitations for Small Depth Circuits","author":"J. H\u00e5stad","year":"1987","unstructured":"J. H\u00e5stad. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA, 1987."},{"key":"1_CR53","first-page":"231","volume":"71","author":"H. Heller","year":"1986","unstructured":"H. Heller. On relativized exponential and probabilistic complexity classes. Information and Computation, 71:231\u2013243, 1986.","journal-title":"Information and Computation"},{"key":"1_CR54","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J. H\u00e5stad","year":"1991","unstructured":"J. H\u00e5stad and M. Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113\u2013129, 1991.","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, S. Jukna, and P. Pudl\u00e1k. Top-down lower bounds for depth 3 circuits. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 124\u2013129, 1993.","key":"1_CR55","DOI":"10.1109\/SFCS.1993.366875"},{"key":"1_CR56","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A. Hajnal","year":"1993","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, and G. Tur\u00e1n. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46:129\u2013154, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR57","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0304-3975(93)90254-Q","volume":"107","author":"R. Heiman","year":"1993","unstructured":"R. Heiman, I. Newman, and A. Wigderson. On read-once threshold formulae and their randomized decision tree complexity. Theoretical Computer Science, 107:63\u201376, 1993.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"T. Hofmeister. A note on the simulation of exponential threshold weights. In International Conference on Computing and Combinatorics (COCOON), volume 1090 of Lecture Notes in Computer Science, pages 136\u2013141. Springer-Verlag, 1996.","key":"1_CR58","DOI":"10.1007\/3-540-61332-3_146"},{"doi-asserted-by":"crossref","unstructured":"K. Iwama and C. Iwamoto. Parallel complexity hierarchies based on PRAMs and DLOGTIME-uniform circuits. In IEEE Conference on Computational Complexity, pages 24\u201332, 1996.","key":"1_CR59","DOI":"10.1109\/CCC.1996.507665"},{"key":"1_CR60","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, 116:103\u2013116, 1995.","journal-title":"Information and Computation"},{"key":"1_CR61","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"4","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages which capture complexity classes. SIAM J. Comput., 4:760\u2013778, 1987.","journal-title":"SIAM J. Comput."},{"key":"1_CR62","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman. Expressibility and parallel complexity. SIAM Journal on Computing, 18:625\u2013638, 1989.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 236\u2013243, 1989.","key":"1_CR63","DOI":"10.1109\/SFCS.1989.63484"},{"key":"1_CR64","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"N. Jones. Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences, 11:68\u201385, 1975. Corrigendum: Journal of Computer and System Sciences 15:241, 1977.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR65","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(95)00137-2","volume":"56","author":"S. Jukna","year":"1995","unstructured":"S. Jukna. Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates. Information Processing Letters, 56:147\u2013150, 1995.","journal-title":"Information Processing Letters"},{"key":"1_CR66","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40\u201356, 1982.","journal-title":"Information and Control"},{"doi-asserted-by":"crossref","unstructured":"M. Krause and P. Pudl\u00e1k. On the computational power of depth 2 circuits with threshold and modulo gates. In ACM Symposium on Theory of Computing (STOC), pages 48\u201357, 1994.","key":"1_CR67","DOI":"10.1145\/195058.195103"},{"doi-asserted-by":"crossref","unstructured":"M. Krause and P. Pudl\u00e1k. On computing Boolean functions by sparse real polynomials. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 682\u2013691, 1995.","key":"1_CR68","DOI":"10.1109\/SFCS.1995.492670"},{"unstructured":"M. Krause and P. Pudl\u00e1k. More on computing Boolean functions by sparse real polynomials and related types of threshold circuits. Technical Report 622, University of Dortmund, 1996. A preliminary version appeared as [KP95].","key":"1_CR69"},{"doi-asserted-by":"crossref","unstructured":"M. Krause. Geometric arguments yield better bounds for threshold circuits and distributed computing. In Structure in Complexity Theory Conference, pages 314\u2013321, 1991.","key":"1_CR70","DOI":"10.1109\/SCT.1991.160275"},{"key":"1_CR71","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/inco.1993.1033","volume":"104","author":"R. Kannan","year":"1993","unstructured":"R. Kannan, H. Venkateswaran, V. Vinay, and A. Yao. A circuit-based proof of Toda's theorem. Information and Computation, 104:271\u2013276, 1993.","journal-title":"Information and Computation"},{"key":"1_CR72","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/BF01204170","volume":"28","author":"M. Krause","year":"1995","unstructured":"M. Krause and S. Waack. Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. Mathematical Systems Theory, 28:553\u2013564, 1995.","journal-title":"Mathematical Systems Theory"},{"unstructured":"F. Lemieux. Finite Groupoids and their Applications to Computational Complexity. PhD thesis, McGill University, 1996.","key":"1_CR73"},{"doi-asserted-by":"crossref","unstructured":"J. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. In Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 775 of Lecture Notes in Computer Science, pages 415\u2013426. Springer-Verlag, 1994.","key":"1_CR74","DOI":"10.1007\/3-540-57785-8_159"},{"key":"1_CR75","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40:607\u2013620, 1993.","journal-title":"Journal of the ACM"},{"key":"1_CR76","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. Lutz","year":"1992","unstructured":"J. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"A. Maciel. Threshold Circuits of Small Majority-Depth. PhD thesis, McGill University, 1995.","key":"1_CR77"},{"key":"1_CR78","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P. McKenzie","year":"1991","unstructured":"P. McKenzie, P. P\u00e9ladeau, and D. Th\u00e9rien. NC1: The automata-theoretic viewpoint. Computational Complexity, 1:330\u2013359, 1991.","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"A. Maciel and D. Th\u00e9rien. Threshold circuits for iterated multiplication: Using AC0 for free. In Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 665 of Lecture Notes in Computer Science, pages 545\u2013554. Springer-Verlag, 1993.","key":"1_CR79","DOI":"10.1007\/3-540-56503-5_54"},{"key":"1_CR80","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301\u2013313, 1994.","journal-title":"Computational Complexity"},{"key":"1_CR81","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149\u2013167, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR82","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0022-0000(88)90030-X","volume":"36","author":"I. Parberry","year":"1988","unstructured":"I. Parberry and G. Schnitger. Parallel computation with threshold functions. Journal of Computer and System Sciences, 36:278\u2013302, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR83","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0893-6080(89)90015-4","volume":"2","author":"I. Parberry","year":"1989","unstructured":"I. Parberry and G. Schnitger. Relating Boltzmann machines to conventional models of computation. Neural Networks, 2:59\u201367, 1989.","journal-title":"Neural Networks"},{"key":"1_CR84","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01212982","volume":"14","author":"J. Radhakrishnan","year":"1994","unstructured":"J. Radhakrishnan. \u03c3\u03c0\u03c3 threshold formulas. Combinatorica, 14:345\u2013374, 1994.","journal-title":"Combinatorica"},{"key":"1_CR85","first-page":"598","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. A. Razborov. Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41:598\u2013607, 1987. English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333\u2013338, 1987.","journal-title":"Mathematicheskie Zametki"},{"doi-asserted-by":"crossref","unstructured":"A. A. Razborov. On small depth threshold circuits. In Scandinavian Workshop on Algorithm Theory (SWAT), volume 621 of Lecture Notes in Computer Science, pages 42\u201352. Springer-Verlag, 1992.","key":"1_CR86","DOI":"10.1007\/3-540-55706-7_4"},{"doi-asserted-by":"crossref","unstructured":"A. A. Razborov. Bounded arithmetic and lower bounds. In P. Clote and J. Remmel, editors, Feasible Mathematics II, volume 13 of Progress in Computer Science and Applied Logic, pages 344\u2013386. Birkh\u00c4user, 1995.","key":"1_CR87","DOI":"10.1007\/978-1-4612-2566-9_12"},{"doi-asserted-by":"crossref","unstructured":"A. A. Razborov and S. Rudich. Natural proofs. In Proceedings, 26th ACM Symposium on Theory of Computing, pages 204\u2013213, 1994.","key":"1_CR88","DOI":"10.1145\/195058.195134"},{"doi-asserted-by":"crossref","unstructured":"K. Regan, D. Sivakumar, and J.-Y. Cai. Pseudorandom generators, measure theory, and natural proofs. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 26\u201335, 1995.","key":"1_CR89","DOI":"10.1109\/SFCS.1995.492459"},{"doi-asserted-by":"crossref","unstructured":"V. Roychowdhury, K.-Y. Siu, and A. Orlitsky, editors. Theoretical Advances in Neural Computation and Learning. Kluwer, 1994.","key":"1_CR90","DOI":"10.1007\/978-1-4615-2696-4"},{"key":"1_CR91","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/inco.1995.1095","volume":"120","author":"V. Roychowdhury","year":"1995","unstructured":"V. Roychowdhury, K.-Y. Siu, A. Orlitsky, and T. Kailath. Vector analysis of threshold functions. Information and Computation, 120:22\u201331, 1995.","journal-title":"Information and Computation"},{"key":"1_CR92","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0020-0190(93)90041-7","volume":"45","author":"A. A. Razborov","year":"1993","unstructured":"A. A. Razborov and A. Wigderson. n \u03a9(logn) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Information Processing Letters, 45:303\u2013307, 1993.","journal-title":"Information Processing Letters"},{"unstructured":"M. Sitharam. Approximation from linear spaces, lower bounds, pseudorandomness, and learning. Submitted.","key":"1_CR93"},{"key":"1_CR94","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/BF01206321","volume":"5","author":"M. Sitharam","year":"1995","unstructured":"M. Sitharam. Pseudorandom generators and learning algorithms for AC0. Computational Complexity, 5:248\u2013266, 1995.","journal-title":"Computational Complexity"},{"key":"1_CR95","volume-title":"PhD thesis","author":"D. Sivakumar","year":"1996","unstructured":"D. Sivakumar. Probabilistic Techniques in Structural Complexity Theory. PhD thesis, SUNY Buffalo, 1996."},{"doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings, 19th ACM Symposium on Theory of Computing, pages 77\u201382, 1987.","key":"1_CR96","DOI":"10.1145\/28395.28404"},{"doi-asserted-by":"crossref","unstructured":"R. Smolensky. On representations by low-degree polynomials. In IEEE Symposium on Foundations of Computer Science (FOCS), 1993.","key":"1_CR97","DOI":"10.1109\/SFCS.1993.366874"},{"unstructured":"L. Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Mass. Inst. of Technology, 1974.","key":"1_CR98"},{"key":"1_CR99","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2273858","volume":"52","author":"L. Stockmeyer","year":"1987","unstructured":"L. Stockmeyer. Classifying the computational complexity of problems. Journal of Symbolic Logic, 52:1\u201343, 1987.","journal-title":"Journal of Symbolic Logic"},{"key":"1_CR100","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0304-3975(93)90214-E","volume":"113","author":"J. Tarui","year":"1993","unstructured":"J. Tarui. Probabilistic polynomials, AC0 functions, and the polynomial-time hierarchy. Theoretical Computer Science, 113:167\u2013183, 1993.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"G. Tardos and D. A. Mix Barrington. A lower bound on the MOD 6 degree of the OR function. In Proc. 3rd Israel Symposium on the Theory of Computing and Systems, pages 52\u201356. IEEE Press, 1995.","key":"1_CR101","DOI":"10.1109\/ISTCS.1995.377046"},{"key":"1_CR102","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF01263425","volume":"4","author":"D. Th\u00e9rien","year":"1994","unstructured":"D. Th\u00e9rien. Circuits constructed with MODq gates cannot compute AND in sublinear size. Computational Complexity, 4:383\u2013388, 1994.","journal-title":"Computational Complexity"},{"key":"1_CR103","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20:865\u2013877, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR104","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1137\/S0895480193255505","volume":"9","author":"S.-C. Tsai","year":"1996","unstructured":"S.-C. Tsai. Lower bounds on representing Boolean functions as polynomials in z m . SIAM Journal on Discrete Mathematics, 9:55\u201362, 1996.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"1_CR105","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. Wilson","year":"1985","unstructured":"C. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31:169\u2013181, 1985.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"A. Yao. Separating the polynomial-time hierarchy by oracles. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 1\u201310, 1985.","key":"1_CR106","DOI":"10.1109\/SFCS.1985.49"},{"doi-asserted-by":"crossref","unstructured":"A. Yao. On ACC and threshold circuits. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 619\u2013627, 1990.","key":"1_CR107","DOI":"10.1109\/FSCS.1990.89583"},{"key":"1_CR108","first-page":"117","volume":"112","author":"P.Y. Yan","year":"1994","unstructured":"P.Y. Yan and I. Parberry. Exponential size lower bounds for some depth three circuits. Information and Computation (formerly Information and Control), 112:117\u2013130, 1994.","journal-title":"Information and Computation (formerly Information and Control)"},{"doi-asserted-by":"crossref","unstructured":"Z.-L. Zhang, D. A. Mix Barrington, and J. Tarui. Computing symmetric functions with AND\/OR circuits and a single MAJORITY gate. In 10th Annual Symposium on Theoretical Aspects of Computer Science, volume 665 of Lecture Notes in Computer Science, pages 535\u2013544. Springer-Verlag, 1993.","key":"1_CR109","DOI":"10.1007\/3-540-56503-5_53"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62034-6_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:28:11Z","timestamp":1742599691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62034-6_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620341","9783540496311"],"references-count":109,"URL":"https:\/\/doi.org\/10.1007\/3-540-62034-6_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}