{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T13:04:44Z","timestamp":1768914284144,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,2,3]],"date-time":"2012-02-03T00:00:00Z","timestamp":1328227200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00037-011-0034-0","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T18:37:51Z","timestamp":1328639871000},"page":"83-127","source":"Crossref","is-referenced-by-count":23,"title":["On the security of Goldreich\u2019s one-way function"],"prefix":"10.1007","volume":"21","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youming","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,3]]},"reference":[{"issue":"6","key":"34_CR1","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"Noga. Alon","year":"1997","unstructured":"Alon Noga., Kahale Nabil (1997) A Spectral Technique for Coloring Random 3-Colorable Graphs. SIAM J. Comp 26(6): 1733\u20131748 ISSN 0097-5397","journal-title":"SIAM J. Comp"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Boaz Barak & Avi Wigderson (2010). Public-key cryptography from different assumptions. In STOC \u201910: Proceedings of the 42nd ACM symposium on Theory of computing, 171\u2013180. ACM, New York, NY, USA. ISBN 978-1-4503-0050-6.","DOI":"10.1145\/1806689.1806715"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2004). Cryptography in NC 0. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, 166\u2013175.","DOI":"10.1109\/FOCS.2004.20"},{"key":"34_CR4","unstructured":"Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2006). On Pseudorandom Generators with Linear Stretch in NC 0. In Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM 2006), 260\u2013271."},{"key":"34_CR5","unstructured":"Andrej Bogdanov & Youming Qiao (2009). On the Security of Goldreich\u2019s One-Way Function. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 392\u2013405."},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Moses Charikar & Anthony Wirth (2004). Maximizing Quadratic Programs: Extending Grothendieck\u2019s Inequality. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science, 54\u201360.","DOI":"10.1109\/FOCS.2004.39"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"James Cook, Omid Etesami, Rachel Miller & Luca Trevisan (2009). Goldreich\u2019s One-Way Function Candidate and Myopic Backtracking Algorithms. In Proceedings of the 6th Theory of Cryptography Conference (TCC), 521\u2013538.","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"34_CR8","unstructured":"Abraham Flaxman (2003). A spectral technique for random satisfiable 3CNF formulas. In SODA \u201903: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 357\u2013363. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. ISBN 0-89871-538-5."},{"issue":"6","key":"34_CR9","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"Michel X. Goemans","year":"1995","unstructured":"Goemans Michel X., Williamson David P. (1995) Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115\u20131145","journal-title":"J. ACM"},{"key":"34_CR10","unstructured":"Oded Goldreich (2000a). Candidate one-way functions based on expander graphs. Technical report, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"34_CR11","volume-title":"Foundations of Cryptography: Basic Tools","author":"Oded Goldreich","year":"2000","unstructured":"Goldreich Oded (2000) Foundations of Cryptography: Basic Tools. Cambridge University Press, New York, NY, USA ISBN0-52-179172-3"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Michael Krivelevich & Dan Vilenchik (2006). Solving random satisfiable 3CNF formulas in expected polynomial time. In SODA \u201906: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, 454\u2013463. ACM, New York, NY, USA. ISBN 0-89871-605-5.","DOI":"10.1145\/1109557.1109608"},{"key":"34_CR13","unstructured":"Elchanan Mossel, Amir Shpilka & Luca Trevisan (2003). On $${\\varepsilon}$$ -Biased Generators in NC 0. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 136\u2013145."},{"issue":"1","key":"34_CR14","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02579445","volume":"5","author":"Jeanette P. Schmidt","year":"1985","unstructured":"Schmidt Jeanette P., Shamir Eli (1985) Component structure in the evolution of random hypergraphs. Combinatorica 5(1): 81\u201394","journal-title":"Combinatorica"},{"key":"34_CR15","unstructured":"G. W. Stewart & Ji-guang Sun (1990). Matrix Perturbation Theory. Academic Press, Inc. ISBN 0-12-670230-6."},{"key":"34_CR16","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/SAT190033","volume":"3","author":"Danny Vilenchik","year":"2007","unstructured":"Vilenchik Danny (2007) It\u2019s all about the support: a new perspective on the satisfiability problem. Journal on Satisfiability, Boolean Modeling, and Computation 3: 125\u2013139","journal-title":"Journal on Satisfiability, Boolean Modeling, and Computation"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0034-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0034-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0034-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,1]],"date-time":"2020-07-01T21:47:03Z","timestamp":1593640023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0034-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["34"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0034-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,3]]}}}