{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T12:08:56Z","timestamp":1768910936623,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,8]],"date-time":"2015-04-08T00:00:00Z","timestamp":1428451200000},"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":["J Cryptol"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00145-015-9202-8","type":"journal-article","created":{"date-parts":[[2015,4,7]],"date-time":"2015-04-07T19:35:47Z","timestamp":1428435347000},"page":"577-596","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A Dichotomy for Local Small-Bias Generators"],"prefix":"10.1007","volume":"29","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"given":"Andrej","family":"Bogdanov","sequence":"additional","affiliation":[]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,8]]},"reference":[{"key":"9202_CR1","unstructured":"M. Alekhnovich, More on average case vs approximation complexity, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003), pp. 298\u2013307"},{"key":"9202_CR2","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich, E. Ben-Sasson, A.A. Razborov, A. Wigderson, Pseudorandom generators in propositional proof complexity. SIAM Journal of Computation 34(1):67\u201388, 2004","DOI":"10.1137\/S0097539701389944"},{"key":"9202_CR3","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich, E. A. Hirsch, D. Itsykson, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reasoning 35(1\u20133):51\u201372, 2005","DOI":"10.1007\/s10817-005-9006-x"},{"issue":"5","key":"9202_CR4","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/120884857","volume":"42","author":"B Applebaum","year":"2013","unstructured":"B. Applebaum, Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM Journal of Computation 42(5):2008\u20132037, 2013.","journal-title":"SIAM Journal of Computation"},{"key":"9202_CR5","unstructured":"B. Applebaum, B. Barak, A. Wigderson, Public-key cryptography from different assumptions, in 42nd ACM Symposium on Theory of Computing (STOC 2010) (2010), pp. 171\u2013180"},{"key":"9202_CR6","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in \n                    \n                      \n                    \n                    $$\\text{ NC }^{0}$$\n                    \n                      \n                        \n                          \n                          NC\n                          \n                            \n                            0\n                          \n                        \n                      \n                    \n                  . Journal of Computational Complexity 36(4):845\u2013888, 2006","DOI":"10.1137\/S0097539705446950"},{"key":"9202_CR7","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, On pseudorandom generators with linear stretch in \n                    \n                      \n                    \n                    $$\\text{ NC }^0$$\n                    \n                      \n                        \n                          \n                          NC\n                          \n                            \n                            0\n                          \n                        \n                      \n                    \n                  . Journal of Computational Complexity 17(1):38\u201369, 2008","DOI":"10.1007\/s00037-007-0237-6"},{"key":"9202_CR8","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography with constant input locality. Journal of Cryptology 22(4), 429\u2013469, 2009","DOI":"10.1007\/s00145-009-9039-0"},{"key":"9202_CR9","unstructured":"S. Arora, R. Ge, New algorithms for learning in presence of errors. in ICALP (1) (2011), pp. 403\u2013415"},{"key":"9202_CR10","unstructured":"E. Ben-Sasson, A. Wigderson, Short proofs are narrow\u2013resolution made simple. in STOC (1999), pp. 517\u2013526"},{"key":"9202_CR11","unstructured":"A. Bogdanov, P. Papakonstantinou, A. Wan, Pseudorandomness for read-once formulas. in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (2011), pp. 240\u2013246"},{"issue":"1","key":"9202_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00037-011-0034-0","volume":"21","author":"A Bogdanov","year":"2012","unstructured":"A. Bogdanov, Y. Qiao, On the security of Goldreich\u2019s one-way function. Computational Complexity 21(1):83\u2013127, 2012.","journal-title":"Computational Complexity"},{"key":"9202_CR13","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00145-011-9117-y","volume":"26","author":"A Bogdanov","year":"2013","unstructured":"A. Bogdanov, A. Rosen, Input locality and hardness amplification. Journal of Cryptology 26:144\u2013171, 2013.","journal-title":"Journal of Cryptology"},{"key":"9202_CR14","doi-asserted-by":"crossref","unstructured":"A. Bogdanov, E. Viola, Pseudorandom bits for polynomials. SIAM J. Comput. 39(6), 2464\u20132486 (2010)","DOI":"10.1137\/070712109"},{"key":"9202_CR15","unstructured":"M. Braverman, Poly-logarithmic independence fools AC\n                    \n                      \n                    \n                    $$^0$$\n                    \n                      \n                        \n                          \n                          0\n                        \n                      \n                    \n                   circuits, in Annual IEEE Conference on Computational Complexity (2009), pp. 3\u20138"},{"key":"9202_CR16","doi-asserted-by":"crossref","unstructured":"J. Cook, O. Etesami, R. Miller, L. Trevisan, Goldreich\u2019s one-way function candidate and myopic backtracking algorithms. in TCC, ed. by O. Reingold, Lecture Notes in Computer Science, vol 5444 (Springer, Berlin, 2009), pp. 521\u2013538","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"9202_CR17","doi-asserted-by":"crossref","unstructured":"M. Cryan, P.B. Miltersen, On pseudorandom generators in NC\n                    \n                      \n                    \n                    $$^0$$\n                    \n                      \n                        \n                          \n                          0\n                        \n                      \n                    \n                  , in Proceedings of 26th MFCS (2001)","DOI":"10.1007\/3-540-44683-4_24"},{"key":"9202_CR18","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, P. Gopalan, R. Jaiswal, R.A. Servedio, E. Viola, Bounded independence fools halfspaces. SIAM Journal of Computation 39(8):3441\u20133462, 2010","DOI":"10.1137\/100783030"},{"key":"9202_CR19","unstructured":"I. Diakonikolas, D.M. Kane, J. Nelson, Bounded independence fools degree-2 threshold functions, in FOCS (2010), pp. 11\u201320"},{"key":"9202_CR20","unstructured":"S.O. Etesami, Pseudorandomness Against Depth-2 Circuits and Analysis of Goldreich\u2019s Candidate One-Way Function. Technical Report EECS-2010-180, UC Berkeley (2010)"},{"key":"9202_CR21","doi-asserted-by":"crossref","unstructured":"M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM: Journal of the ACM, 42:1115\u20131145, 1995","DOI":"10.1145\/227683.227684"},{"key":"9202_CR22","unstructured":"O. Goldreich, Candidate one-way functions based on expander graphs. in Electronic Colloquium on Computational Complexity (ECCC) (2000) 7(090)"},{"key":"9202_CR23","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Three XOR-lemmas\u2013an exposition, in Studies in Complexity and Cryptography, ed. by O. Goldreich, Lecture Notes in Computer Science, vol 6650 (Springer, Berlin, 2011), pp. 248\u2013272","DOI":"10.1007\/978-3-642-22670-0_22"},{"key":"9202_CR24","unstructured":"R. Impagliazzo, N. Nisan, A. Wigderson, Pseudorandomness for network algorithms, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing (1994), pp. 356\u2013364"},{"key":"9202_CR25","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Cryptography with constant computational overhead. in STOC, ed. by R.E. Ladner, C. Dwork (ACM, New York, 2008), pp. 433\u2013442","DOI":"10.1145\/1374376.1374438"},{"key":"9202_CR26","unstructured":"D. Itsykson, Lower bound on average-case complexity of inversion of Goldreich\u2019s function by drunken backtracking algorithms, in Computer Science-Theory and Applications, 5th International Computer Science Symposium in Russia (2010), pp. 204\u2013215"},{"key":"9202_CR27","unstructured":"R. Miller, Goldreich\u2019s one-way function candidate and drunken backtracking algorithms. Distinguished major thesis (University of Virginia, Virginia, 2009)"},{"key":"9202_CR28","unstructured":"E. Mossel, A. Shpilka, L. Trevisan, On \n                    \n                      \n                    \n                    $$\\epsilon $$\n                    \n                      \n                        \u03f5\n                      \n                    \n                  -biased generators, in NC\n                    \n                      \n                    \n                    $$^{0}$$\n                    \n                      \n                        \n                          \n                          0\n                        \n                      \n                    \n                  . in Proceedings of 44th FOCS (2003), pp. 136\u2013145"},{"key":"9202_CR29","unstructured":"J. Naor, M. Naor, Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing, 22(4):838\u2013856, 1993. Preliminary version in Proc. of 22th STOC, 1990"},{"key":"9202_CR30","unstructured":"S. K. Panjwani, An Experimental Evaluation of Goldreich\u2019s One-Way Function. Technical report, IIT, Bombay, 2001"},{"key":"9202_CR31","doi-asserted-by":"crossref","unstructured":"T. Siegenthaler, Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory 30(5):776\u2013778 (1984)","DOI":"10.1109\/TIT.1984.1056949"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9202-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-015-9202-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9202-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-015-9202-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:22:24Z","timestamp":1586334144000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-015-9202-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,8]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9202"],"URL":"https:\/\/doi.org\/10.1007\/s00145-015-9202-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,8]]},"assertion":[{"value":"4 September 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2015","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}