{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:44Z","timestamp":1725456764061},"publisher-location":"Berlin\/Heidelberg","reference-count":15,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029603","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"158-164","source":"Crossref","is-referenced-by-count":9,"title":["On the power of uniform families of constant depth threshold circuits"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Hertrampf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"L. Adleman, Two theorems on random polynomial time, Proc. 19th IEEE Symposium on Foundations of Computer Science, pp. 75\u201383.","key":"12_CR1","DOI":"10.1109\/SFCS.1978.37"},{"doi-asserted-by":"crossref","unstructured":"E. Allender, A note on the power of threshold circuits, Proc. 30th IEEE Symposium on Foundations of Computer Science, pp. 580\u2013584.","key":"12_CR2","DOI":"10.1109\/SFCS.1989.63538"},{"doi-asserted-by":"crossref","unstructured":"E. Allender, P-uniform circuit complexity, J. ACM 36, 912\u2013928.","key":"12_CR3","DOI":"10.1145\/76359.76370"},{"doi-asserted-by":"crossref","unstructured":"D. A. Mix Barrington, N. Immerman, and H. Straubing, On uniformity within NC 1, Proc. 3rd IEEE Structure in Complexity Theory Conference, pp. 47\u201359.","key":"12_CR4","DOI":"10.1016\/0022-0000(90)90022-D"},{"unstructured":"J. Bruck and C. Smolensky, Polynomial threshold functions, AC 0 functions, and spectral norms, Tech. Report RJ 7140 (67387) IBM, Yorktown Heights.","key":"12_CR5"},{"doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, G. Tur\u00e1n, Threshold circuits of bounded depth, Proc. 28th IEEE Symposium on Foundations of Computer Science, pp. 99\u2013110.","key":"12_CR6","DOI":"10.1109\/SFCS.1987.59"},{"unstructured":"J. H\u00e5stad, Computational limitations for small-depth circuits, Doctoral Dissertation, MIT.","key":"12_CR7"},{"doi-asserted-by":"crossref","unstructured":"C. Lautemann, BPP and the polynomial hierarchy, Information Processing Letters 17, 215\u2013217.","key":"12_CR8","DOI":"10.1016\/0020-0190(83)90044-3"},{"doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson, Hardness vs. randomness, Proc. 29th IEEE Symposium on Foundations of Computer Science, pp. 2\u201311.","key":"12_CR9","DOI":"10.1109\/SFCS.1988.21916"},{"doi-asserted-by":"crossref","unstructured":"I. Parberry and G. Schnitger, Parallel computation with threshold functions, J. Computer and System Science 36, 278\u2013302.","key":"12_CR10","DOI":"10.1016\/0022-0000(88)90030-X"},{"doi-asserted-by":"crossref","unstructured":"A. A. Razborov, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Mathematicheskie Zametki 41(4), 598\u2013607. English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:4, 333\u2013338.","key":"12_CR11","DOI":"10.1007\/BF01137685"},{"doi-asserted-by":"crossref","unstructured":"W. Ruzzo, On Uniform Circuit Complexity, J. Comput. and System Sci. 21, 365\u2013383.","key":"12_CR12","DOI":"10.1016\/0022-0000(81)90038-6"},{"doi-asserted-by":"crossref","unstructured":"M. Sipser, A complexity theoretic approach to randomness, Proc. 15th Annual ACM Symposium on Theory of Computing, pp. 330\u2013335.","key":"12_CR13","DOI":"10.1145\/800061.808762"},{"doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proc. 19th ACM Symposium on Theory of Computing, pp. 77\u201382.","key":"12_CR14","DOI":"10.1145\/28395.28404"},{"doi-asserted-by":"crossref","unstructured":"L. Valiant and V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science 47, 85\u201393.","key":"12_CR15","DOI":"10.1016\/0304-3975(86)90135-0"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:15:39Z","timestamp":1586592939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0029603","relation":{},"subject":[]}}