{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:15:33Z","timestamp":1649070933552},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"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":[[1995,9]]},"DOI":"10.1007\/bf01206321","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T14:33:05Z","timestamp":1109255585000},"page":"248-266","source":"Crossref","is-referenced-by-count":1,"title":["Pseudorandom generators and learning algorithms forAC 0"],"prefix":"10.1007","volume":"5","author":[{"given":"Meera","family":"Sitharam","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Bellare, A technique for upper bounding the spectral norm with applications to learning. InProc. 5 th Ann. IEEE Symp. on Computational Learning Theory (COLT), 1992, 62?70.","DOI":"10.1145\/130385.130392"},{"issue":"2","key":"CR2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck, Harmonic analysis of polynomial threshold functions.SIAM Journal of Discrete Mathematics,3:2 (1990), 168?177.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser,The complexity of finite functions. Technical Report MIT\/LCS\/TM-405, Massachussetts Institute of Technology, Laboratory for Computer Sciences, 1989.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"issue":"1","key":"CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck andR. Smolensky, Polynomial Threshold Functions, AC0 Functions and Spectral Norms.SIAM Journal of Computing,21:1 (1992), 33?42.","journal-title":"SIAM Journal of Computing"},{"key":"CR5","unstructured":"H. Dym and H.P. McKean,Fourier series and integrals. Probability and Mathematical Statistics series, Academic Press, 1972."},{"key":"CR6","unstructured":"M. Down and M. Sitharam,Shannon bounds for functions over ? n 2 . Technical Report #90-12-1, Kent State University, Department of Mathematics and Computer Science, 1990."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Jackson, and S. Smith, Improved learning ofAC 0 functions. InProc. 5 th Ann. IEEE Symp. on Computational Learning Theory (COLT), 1992, 317?325.","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, andM. Sipser, Parity, circuits and the polynomial time hierarchy.Mathematical Systems Theory 17 (1984), 17?27.","journal-title":"Mathematical Systems Theory"},{"key":"CR9","unstructured":"J. H\u00e5stad,Computational limitations of small depth circuits. Ph.D. thesis, Massachussetts Institute of Technology press, 1986."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. Kahn, J. Kalai, and N. Linial, The influence of variables on Boolean functions.Proc. 29 th Ann. IEEE Symp. Foundations of Computer Science (FOCS), 1988, 68?80.","DOI":"10.1109\/SFCS.1988.21923"},{"issue":"6","key":"CR11","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"E. Kushilevitz andY. Mansour, Learning decision trees using the Fourier transform.SIAM Journal of Computing 22:6 (1993), 1331?1348.","journal-title":"SIAM Journal of Computing"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transforms, and learnability. InProc. 30 th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), 1989, 574?579. To appear inJACM.","DOI":"10.1109\/SFCS.1989.63537"},{"issue":"4","key":"CR13","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N. Linial","year":"1990","unstructured":"N. Linial andN. Nisan, Approximate inclusion-exclusion.Combinatorica 10:4 (1990), 349?365.","journal-title":"Combinatorica"},{"key":"CR14","unstructured":"F.J. MacWiliams and N.J.A. Sloane,The theory of error-correcting codes. North Holland, 1977."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"N. Nisan and A.W. Widgerson, Hardness vs. randomness. InProc. 29 th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), 1988, 2?11. To appear inJCSS.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials. InProc. 24 th Ann. ACM Symp. on Theory of Computing, 1992, 462?467.","DOI":"10.1145\/129712.129757"},{"key":"CR17","first-page":"354","volume":"31","author":"A.A. Razborov","year":"1985","unstructured":"A.A. Razborov, Lower bounds on the monotone complexity of some Boolean functions.Soviet Mathematics Doklady,31 (1985), 354?357.","journal-title":"Soviet Mathematics Doklady"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"C.E. Shannon, Communication in the presence of noise. InProceedings of the IEEE,37 (1949), 10?21.","DOI":"10.1109\/JRPROC.1949.232969"},{"issue":"3","key":"CR19","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0404038","volume":"4","author":"K.I. Siu","year":"1991","unstructured":"K.I. Siu andJ. Bruck, On the power of threshold circuits with small weights.SIAM Journal of Discrete Mathematics,4:3 (1991), 423?435.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Lower bounds by probabilistic arguments. InProc. 24 th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), 1983, 420?428.","DOI":"10.1109\/SFCS.1983.30"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Separating the polynomial time hierarchy by oracles. InProc. 26 th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), 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\/BF01206321.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206321\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T15:07:32Z","timestamp":1625497652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":21,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01206321"],"URL":"https:\/\/doi.org\/10.1007\/bf01206321","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}