{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:13Z","timestamp":1750220773663,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["257575"],"award-info":[{"award-number":["257575"]}]},{"name":"ISF","award":["552\/16"],"award-info":[{"award-number":["552\/16"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            We construct a pseudorandom generator that fools known-order read-\n            <jats:italic>k<\/jats:italic>\n            oblivious branching programs and, more generally, any linear length oblivious branching program. For polynomial width branching programs, the seed lengths in our constructions are\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\u22121\/2<\/jats:sup>\n            <jats:sup>\n              <jats:italic>k\u22121<\/jats:italic>\n            <\/jats:sup>\n            ) (for the read-\n            <jats:italic>k<\/jats:italic>\n            case) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/ log log\n            <jats:italic>n<\/jats:italic>\n            ) (for the linear length case). Previously, the best construction for these models required seed length (1 \u2212 \u03a9(1))\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3378663","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T11:08:20Z","timestamp":1583320100000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Pseudorandom Bits for Oblivious Branching Programs"],"prefix":"10.1145","volume":"12","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Bombay, Powai, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[{"name":"Center for the Mathematics of Information, California Institute of Technology, Pasadena, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Matthew Anderson Michael A. Forbes Ramprasad Saptharishi Amir Shpilka and Ben Lee Volk. 2018. Identity testing and lower bounds for read-k oblivious algebraic branching programs. TOCT 10 1 (2018) 3:1--3:30. DOI:https:\/\/doi.org\/10.1145\/3170709  Matthew Anderson Michael A. Forbes Ramprasad Saptharishi Amir Shpilka and Ben Lee Volk. 2018. Identity testing and lower bounds for read- k oblivious algebraic branching programs. TOCT 10 1 (2018) 3:1--3:30. DOI:https:\/\/doi.org\/10.1145\/3170709","DOI":"10.1145\/3170709"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.57"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_38"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875673"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.04.013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.23"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913)","year":"2013","author":"Michael","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1129088"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230630"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993672"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"volume-title":"Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM\u201913)","author":"Reingold Omer","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5 (March 2010) 207--388. DOI:https:\/\/doi.org\/10.1561\/0400000039  Amir Shpilka and Amir Yehudayoff. 2010. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5 (March 2010) 207--388. DOI:https:\/\/doi.org\/10.1561\/0400000039","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_20_1","first-page":"83","article-title":"Pseudorandomness for permutation branching programs without the group theory","volume":"19","author":"Steinke Thomas","year":"2012","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a012"},{"key":"e_1_2_1_22_1","volume-title":"An International Symposiumon Symbolic and Algebraic Computation (Lecture Notes in Computer Science)","volume":"72","author":"Zippel Richard","year":"1979"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3378663","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3378663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:19Z","timestamp":1750200079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3378663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,10]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3378663"],"URL":"https:\/\/doi.org\/10.1145\/3378663","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,2,10]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}