{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:38:00Z","timestamp":1770982680378,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642289132","type":"print"},{"value":"9783642289149","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28914-9_34","type":"book-chapter","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T21:12:39Z","timestamp":1330981959000},"page":"600-617","source":"Crossref","is-referenced-by-count":23,"title":["A Dichotomy for Local Small-Bias Generators"],"prefix":"10.1007","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"given":"Andrej","family":"Bogdanov","sequence":"additional","affiliation":[]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: FOCS, pp. 298\u2013307. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"issue":"1","key":"34_CR2","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0097539701389944","volume":"34","author":"M. Alekhnovich","year":"2004","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. SIAM Journal of Computation\u00a034(1), 67\u201388 (2004)","journal-title":"SIAM Journal of Computation"},{"issue":"1-3","key":"34_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10817-005-9006-x","volume":"35","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reasoning\u00a035(1-3), 51\u201372 (2005)","journal-title":"J. Autom. Reasoning"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. Electronic Colloquium on Computational Complexity (ECCC) 18 (2011)","DOI":"10.1145\/2213977.2214050"},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: 42nd ACM Symposium on Theory of Computing (STOC 2010), pp. 171\u2013180 (2010)","DOI":"10.1145\/1806689.1806715"},{"issue":"4","key":"34_CR6","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM Journal on Computing\u00a036(4), 845\u2013888 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"34_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00037-007-0237-6","volume":"17","author":"B. Applebaum","year":"2008","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. Journal of Computational Complexity\u00a017(1), 38\u201369 (2008)","journal-title":"Journal of Computational Complexity"},{"issue":"4","key":"34_CR8","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-009-9039-0","volume":"22","author":"B. Applebaum","year":"2009","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. Journal of Cryptology\u00a022(4), 429\u2013469 (2009)","journal-title":"Journal of Cryptology"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S. Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New Algorithms for Learning in Presence of Errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 403\u2013415. Springer, Heidelberg (2011)"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow - resolution made simple. In: STOC, pp. 517\u2013526 (1999)","DOI":"10.1145\/301250.301392"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Papakonstantinou, P., Wan, A.: Pseudorandomness for read-once formulas. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (2011) (to appear)","DOI":"10.1109\/FOCS.2011.57"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-03685-9_30","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Bogdanov","year":"2009","unstructured":"Bogdanov, A., Qiao, Y.: On the Security of Goldreich\u2019s One-Way Function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 392\u2013405. Springer, Heidelberg (2009)"},{"key":"34_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-19571-6_1","volume-title":"Theory of Cryptography","author":"A. Bogdanov","year":"2011","unstructured":"Bogdanov, A., Rosen, A.: Input Locality and Hardness Amplification. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 1\u201318. Springer, Heidelberg (2011)"},{"issue":"6","key":"34_CR14","doi-asserted-by":"publisher","first-page":"2464","DOI":"10.1137\/070712109","volume":"39","author":"A. Bogdanov","year":"2010","unstructured":"Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. SIAM J. Comput.\u00a039(6), 2464\u20132486 (2010)","journal-title":"SIAM J. Comput."},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Poly-logarithmic independence fools AC0 circuits. In: Annual IEEE Conference on Computational Complexity, pp. 3\u20138 (2009)","DOI":"10.1109\/CCC.2009.35"},{"key":"34_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-642-00457-5_31","volume-title":"Theory of Cryptography","author":"J. Cook","year":"2009","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich\u2019s One-Way Function Candidate and Myopic Backtracking Algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 521\u2013538. Springer, Heidelberg (2009)"},{"key":"34_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-44683-4_24","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M. Cryan","year":"2001","unstructured":"Cryan, M., Miltersen, P.B.: On Pseudorandom Generators in NC0. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 272\u2013284. Springer, Heidelberg (2001)"},{"issue":"8","key":"34_CR18","doi-asserted-by":"publisher","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"I. Diakonikolas","year":"2010","unstructured":"Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R.A., Viola, E.: Bounded independence fools halfspaces. SIAM Journal of Computation\u00a039(8), 3441\u20133462 (2010)","journal-title":"SIAM Journal of Computation"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Nelson, J.: Bounded independence fools degree-2 threshold functions. In: FOCS, pp. 11\u201320 (2010)","DOI":"10.1109\/FOCS.2010.8"},{"key":"34_CR20","unstructured":"Etesami, S.O.: Pseudorandomness against depth-2 circuits and analysis of goldreich\u2019s candidate one-way function. Technical Report EECS-2010-180, UC Berkeley (2010)"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM: Journal of the ACM\u00a042 (1995)","DOI":"10.1145\/227683.227684"},{"key":"34_CR22","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(090) (2000)"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"34_CR24","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 433\u2013442. ACM (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"Itsykson, D.: 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, pp. 204\u2013215 (2010)","DOI":"10.1007\/978-3-642-13182-0_19"},{"key":"34_CR26","unstructured":"Miller, R.: Goldreich\u2019s one-way function candidate and drunken backtracking algorithms. Distinguished major thesis, University of Virginia (2009)"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On \u03b5-biased generators in NC0. In: Proc. 44th FOCS, pp. 136\u2013145 (2003)","DOI":"10.1109\/SFCS.2003.1238188"},{"issue":"4","key":"34_CR28","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing\u00a022(4), 838\u2013856 (1993); Preliminary version in Proc. 22th STOC (1990)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR29","unstructured":"Panjwani, S.K.: An experimental evaluation of goldreich\u2019s one-way function. Technical report, IIT, Bombay (2001)"},{"issue":"5","key":"34_CR30","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1109\/TIT.1984.1056949","volume":"30","author":"T. Siegenthaler","year":"1984","unstructured":"Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory\u00a030(5), 776\u2013778 (1984)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28914-9_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T12:03:58Z","timestamp":1742645038000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28914-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642289132","9783642289149"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28914-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}