{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:12Z","timestamp":1750221132831,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1813930"],"award-info":[{"award-number":["1813930"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            Research in the 1980s and 1990s showed how to construct a pseudorandom generator from a function that is hard to compute on more than 99% of the inputs. A more recent line of works showed, however, that if the generator has small error, then the proof of correctness cannot be implemented in subclasses of TC\n            <jats:sup>0<\/jats:sup>\n            , and hence the construction cannot be applied to the known hardness results. This article considers a typical class of pseudorandom generator constructions, and proves an analogous result for the case of large error.\n          <\/jats:p>","DOI":"10.1145\/3322815","type":"journal-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T12:14:26Z","timestamp":1560860066000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Constant-Error Pseudorandomness Proofs from Hardness Require Majority"],"prefix":"10.1145","volume":"11","author":[{"given":"Emanuele","family":"Viola","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0056-2"},{"key":"e_1_2_1_2_1","first-page":"135","article-title":"The expressive power of voting polynomials. Combinatorica","volume":"14","author":"Aspnes James","year":"1994","journal-title":"A Journal on Combinatorics and the Theory of Computing"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00094"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_36"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2215487.2215488"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44666-4_28"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0039-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0003-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_2_1_13_1","first-page":"63","article-title":"Pseudorandom bits for constant depth circuits. Combinatorica","volume":"11","author":"Nisan Noam","year":"1991","journal-title":"A Journal on Combinatorics and the Theory of Computing"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_15_1","first-page":"598","article-title":"Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function","volume":"41","author":"Razborov Alexander","year":"1987","journal-title":"Akademiya Nauk SSSR. Matematicheskie Zametki"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0187-1"},{"key":"e_1_2_1_20_1","unstructured":"Emanuele Viola. 2006. The Complexity of Hardness Amplification and Derandomization. Ph.D. Dissertation. Harvard University.   Emanuele Viola. 2006. The Complexity of Hardness Amplification and Derandomization. Ph.D. Dissertation. Harvard University."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/050640941"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1704803.1704804"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322815","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:26Z","timestamp":1750208546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3322815"],"URL":"https:\/\/doi.org\/10.1145\/3322815","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}