{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:31Z","timestamp":1760202511622,"version":"3.32.0"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1007\/bf01263425","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T02:52:34Z","timestamp":1111632754000},"page":"383-388","source":"Crossref","is-referenced-by-count":10,"title":["Circuits constructed with MOD q gates cannot compute ?AND? in sublinear size"],"prefix":"10.1007","volume":"4","author":[{"given":"Denis","family":"Th\ufffdrien","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","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, 387-1 on finite structures.Annals of Pure and Applied Logic 24 (1983), 1?48.","journal-title":"Annals of Pure and Applied Logic"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"D. A. Mix Barrington, Some problems involving Razborov-Smolensky polynomials. In M. S. Patterson, ed.,Boolean Function Complexity, London Mathematical Society Lecture Notes Series 169, Cambridge University Press, 1992, 109?128.","DOI":"10.1017\/CBO9780511526633.010"},{"issue":"2","key":"CR3","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, andD. Th\u00e9rien, Non-uniform automata over groups.Inform. and Comput. 89 (2) (1990) 109?132.","journal-title":"Inform. and Comput."},{"key":"CR4","first-page":"241","volume":"2","author":"L. Euler","year":"1785","unstructured":"L. Euler,Opusc. analytics Vol. 2 (1785), p. 241.","journal-title":"Opusc. analytics"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"18","author":"M. Furst","year":"1984","unstructured":"M. Furst, J.B. Saxe, andM. Sipser, Parity, circuits and the polynomial-time hierarchy.Math. Systems Theory 18 (1984), 13?27.","journal-title":"Math. Systems Theory"},{"key":"CR6","unstructured":"J. H\u00e5stad, Computational limitations on Small Depth Circuits. Ph.D. Thesis, Massachusetts Institute of Technology, 1986."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01375469","volume":"11","author":"J.D. Kahn","year":"1991","unstructured":"J.D. Kahn, andR. Meshulam, On mod p Traversals.Combinatorica 11 (1991), 17?22.","journal-title":"Combinatorica"},{"issue":"4","key":"CR8","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 additions.Mat. Zametki 41 (4) (1987), 598?607 (in Russian). English translation inMathematical Notes of the Academy of Sciences of the USSR 41 (4) (1987), 333?338.","journal-title":"Mat. Zametki"},{"key":"CR9","unstructured":"M. Szegedy, Algebraic Methods in Lower Bounds for Computational Models with Limited Communication. Ph.D. Thesis, University of Chicago, 1989."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity.In Proc. Nineteenth Ann. ACM Symp. Theor. Comput. (1987), 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"R. Smolensky, On interpolation by analytic functions with special properties and some weak lower bounds on the size of circuits with symmetric gates.In Proc. 31st Ann. Symp. Found. Comput. Sci. (1990), 628?631.","DOI":"10.1109\/FSCS.1990.89584"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"A. Yao, Separating the polynomial-time hierarchy.In Proc. 26th Ann. Symp. Found. Comput. Sci. (1985), 1?10.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01263425.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01263425\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01263425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T08:12:10Z","timestamp":1735373530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01263425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["BF01263425"],"URL":"https:\/\/doi.org\/10.1007\/bf01263425","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}