{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:46Z","timestamp":1725664486366},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_27","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:21Z","timestamp":1330290261000},"page":"319-330","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness"],"prefix":"10.1007","author":[{"given":"Alexander E.","family":"Andreev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea E. F.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 D. P.","family":"Rolim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Allender E. and Strauss M. (1994), \u201cMeasure on Small Complexity Classes, with Applications for BPP\u201d, Proc. of 35th IEEE FOCS, 819\u2013830.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"27_CR2","unstructured":"Alon N. and Spencer J.H. (1992), The Probabilistic Method, Wiley-Interscience Publication."},{"issue":"169","key":"27_CR3","first-page":"147","volume":"127","author":"A.E. Andreev","year":"1985","unstructured":"Andreev A.E. (1985), \u201cThe universal principle of self-correction\u201d, Mat. Sbornik 127(169), N 6, 147\u2013172 (in Russian). English transl. in Math. USSR Sbornik, 55 (1), 145\u2013169 (1986).","journal-title":"Mat. Sbornik"},{"key":"27_CR4","first-page":"251","volume":"1","author":"A.E. Andreev","year":"1989","unstructured":"Andreev A.E. (1989), \u201cOn the complexity of the realizations of partial boolean functions by circuits of functional elements\u201d, J. of Discr. Math. and Appl. 1, 251\u2013262 (1989).","journal-title":"J. of Discr. Math. and Appl."},{"issue":"4","key":"27_CR5","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum M. and Micali S. (1984), \u201cHow to generate cryptographically strong sequences of pseudorandom bits\u201d, J. SIAM, 13(4), 850\u2013864.","journal-title":"J. SIAM"},{"key":"27_CR6","unstructured":"Boppana R. and Hirshfield (1989), \u201cPseudorandom generators and complexity classes\u201d, in Randomness and Computation (S. Micali Ed.), 5, 1\u201326, Adv. in Comput. Res., JAI Press."},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff H. (1952), \u201cA measure of asymptotic efficiency for tests of a hypothesis on the sum of observations\u201d, Ann. Math. Statistic., 23, 493\u2013507.","journal-title":"Ann. Math. Statistic."},{"key":"27_CR8","unstructured":"Feller W. (1970), An Introduction to probability theory and its applications, (Vol. I), III edition, John Wiley and Sons."},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1990","unstructured":"Hagerup T. and Rub C. (1990), \u201cA guided tour of Chernoff bounds\u201d, IPL, 33, 305\u2013308.","journal-title":"IPL"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Kearns M. and Vazirani U. (1994), Topics in Computational Learning Theory, MIT Press.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"27_CR11","first-page":"31","volume":"10","author":"O.B. Lupanov","year":"1965","unstructured":"Lupanov O.B. (1965), \u201cAbout a method circuits design \u2014 local coding principle\u201d, Problemy Kibernet. 10, 31\u2013110 (in Russian). English Translation in Systems Theory Res., 10, 1963.","journal-title":"Problemy Kibernet."},{"key":"27_CR12","first-page":"40","volume":"163","author":"E.I. Nechiporuk","year":"1965","unstructured":"Nechiporuk E.I. (1965), \u201cAbout the complexity of gating circuits for the partial boolean matrix\u201d, Dokl. Akad. Nauk SSSR, 163, 40\u201342 (in Russian). English translation in Soviet Math. Docl.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Nisan N. (1992), Using Hard Problems to Create Pseudorandom Generators, ACM Distinguished Dissertation, MIT Press.","DOI":"10.7551\/mitpress\/7052.001.0001"},{"key":"27_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan N. and Wigderson A. (1994), \u201cHardness vs Randomness\u201d, J. Comput. System Sci. 49, 149\u2013167 (presented also at the 29th IEEE FOCS, 1988).","journal-title":"J. Comput. System Sci."},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01683269","volume":"10","author":"N. Pippenger","year":"1977","unstructured":"Pippenger N. (1977), \u201cInformation theory and the complexity of Boolean functions\u201d, Math. Systems Theory 10, 129\u2013167.","journal-title":"Math. Systems Theory"},{"key":"27_CR16","unstructured":"Razborov A. and Rudich S. (1994), \u201cNatural Proofs\u201d, Proc. of 26th ACM STOC, 204\u2013213, 1994."},{"key":"27_CR17","unstructured":"Regan K.W., Sivakumar D. and Cai J. (1995), \u201cPseudorandom Generators, Measure Theory, and Natural Proofs\u201d, Proc. of the 36th IEEE FOCS, to appear."},{"key":"27_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C.E. Shannon","year":"1949","unstructured":"Shannon, C.E. (1949), \u201cThe synthesis of two-terminal switching circuits\u201d, Bell. Syst. Tech. J. 28, 59\u201398.","journal-title":"Bell. Syst. Tech. J."},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Yao A.C. (1982), \u201cTheory and applications of trapdoor functions\u201d, Proc. of the 23th IEEE FOCS, 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:15:22Z","timestamp":1578536122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_27"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}