{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:51Z","timestamp":1725664191854},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_63","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:00:45Z","timestamp":1330275645000},"page":"71-82","source":"Crossref","is-referenced-by-count":4,"title":["Lower bounds for depth-three circuits with equals and mod-gates"],"prefix":"10.1007","author":[{"given":"Frederic","family":"Green","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"J. Aspnes, R. Beigel, M. Furst, and S. Rudich, The expressive power of voting polynomials. In Proceedings of the 23rd Symposium on Theory of Computing, (1991), 402\u2013409.","DOI":"10.1145\/103418.103461"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender, A note on the power of threshold circuits. In Proceedings of the 30th Symposium on Foundations of Computer Science, (1989), 580\u2013584.","DOI":"10.1109\/SFCS.1989.63538"},{"key":"7_CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"D. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, in Journal of Computer and System Sciences38, (1989), 150\u2013164.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"D. M. Barrington, R. Beigel, and S. Rudich, Representing Boolean functions as polynomials modulo composite numbers, Proceedings of the 24th ACM Symposium on Theory of Computing (1992) 455\u2013461.","DOI":"10.1145\/129712.129756"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"R. Beigel, When do extra majority gates help? polylog(n) majority gates are equivalent to one, in Proceedings of the 24th ACM Symposium on Theory of Computing (1992) 450\u2013454.","DOI":"10.1145\/129712.129755"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, and D. Spielman, PP is closed under intersection, in Proceedings of the 23rd ACM Symposium on the Theory of Computation, (1991), 1\u201311. A journal version is to appear in Journal of Computer and System Sciences.","DOI":"10.1145\/103418.103426"},{"key":"7_CR7","unstructured":"D. M. Barrington, H. Straubing, Complex polynomials and circuit lower bounds for modular counting, to appear in Computational Complexity (also see LATIN '92)."},{"key":"7_CR8","unstructured":"R. Beigel, J. Tarui, On ACC. In Proceedings of the 32nd Symposium on Foundations of Computer Science, (1991), 783\u2013792."},{"key":"7_CR9","unstructured":"J.-Y. Cai, F. Green and T. Thierauf, On the correlation of symmetric functions, to appear in Mathematical Systems Theory."},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow and S. Kurtz, Gap-definable counting classes, in Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press (1991) 30\u201342.","DOI":"10.1109\/SCT.1991.160241"},{"key":"7_CR11","unstructured":"F. Green, J. K\u00f6bler, K. Regan, T. Schwentick, and J. Tor\u00e1n, The power of the middle bit of a #P function, to appear in Journal of Computer and System Sciences. Preliminary versions appeared in Proceedings of the 7th Structure in Complexity Theory Conference, IEEE Computer Society Press, (1992), 111\u2013117, and in Proceedings of the Fourth Italian Conference on Theoretical Computer Science, World-Scientific, Singapore, (1991), 317\u2013329."},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(91)90035-G","volume":"37","author":"F. Green","year":"1991","unstructured":"F. Green, An oracle separating \u2295P from PPPH, Information Processing Letters37 (1991) 149\u2013153.","journal-title":"Information Processing Letters"},{"key":"7_CR13","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01202284","volume":"26","author":"F. Green","year":"1993","unstructured":"F. Green, On the power of deterministic reductions to C=P, in Mathematical Systems Theory26 (1993) 215\u2013233.","journal-title":"Mathematical Systems Theory"},{"key":"7_CR14","volume-title":"Computational limitations of small-depth circuits","author":"J. H\u00e5stad","year":"1987","unstructured":"J. H\u00e5stad, Computational limitations of small-depth circuits, the MIT press, Cambridge, 1987."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, and G. Tur\u00e1n, Threshold circuits of bounded depth, in Proceedings 28th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press (1987) 99\u2013110.","DOI":"10.1109\/SFCS.1987.59"},{"key":"7_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2103-4","volume-title":"A classical introduction to modern number theory","author":"K. Ireland","year":"1990","unstructured":"K. Ireland and M. Rosen, A classical introduction to modern number theory, Second Edition, Springer-Verlag, New York, 1990.","edition":"Second Edition"},{"key":"7_CR17","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 Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, ACM Press (1994) 48\u201357.","DOI":"10.1145\/195058.195103"},{"key":"7_CR18","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, Matematicheskie Zametki41 (1987) 598\u2013607. English translation in Mathematical Notes of the Academy of Sciences of the USSR41 (1987) 333\u2013338.","journal-title":"Matematicheskie Zametki"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing (1987) 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"J. Tarui, Degree complexity of Boolean functions and its applications to relativized separations, in Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press (1991) 382\u2013390.","DOI":"10.1109\/SCT.1991.160282"},{"key":"7_CR21","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. In SIAM Journal on Computing20, (1991) 865\u2013877.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"S.-C. Tsai, Lower bounds on representing Boolean functions as polynomials in Z m , in Proceedings of the Eighth Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press (1993) 96\u2013101.","DOI":"10.1109\/SCT.1993.336537"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:11Z","timestamp":1605648311000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}