{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:22:55Z","timestamp":1778127775046,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_30","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"392-405","source":"Crossref","is-referenced-by-count":29,"title":["On the Security of Goldreich\u2019s One-Way Function"],"prefix":"10.1007","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","reference":[{"key":"30_CR1","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pp. 166\u2013175 (2004)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/11830924_25","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 260\u2013271. Springer, Heidelberg (2006)"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Polylogarithmic independence fools AC0. Technical Report TR09-011, Electronic Colloquium on Computational Complexity (ECCC) (2009)","DOI":"10.1109\/CCC.2009.35"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich\u2019s one-way function candidate and myopic backtracking algorithms. In: Proceedings of the 6th Theory of Cryptography Conference (TCC), pp. 521\u2013538 (2009)","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/11786986_60","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A.: An adaptive spectral heuristic for partitioning random graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 691\u2013702. Springer, Heidelberg (2006)"},{"key":"30_CR6","unstructured":"Flaxman, A.: A spectral technique for random satisfiable 3CNF formulas. In: SODA 2003: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, Maryland, pp. 357\u2013363 (2003)"},{"key":"30_CR7","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. Technical Report TR00-090, Electronic Colloquium on Computational Complexity (ECCC) (2000)"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1145\/1109557.1109608","volume-title":"SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms","author":"M. Krivelevich","year":"2006","unstructured":"Krivelevich, M., Vilenchik, D.: Solving random satisfiable 3CNF formulas in expected polynomial time. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, pp. 454\u2013463. ACM Press, New York (2006)"},{"issue":"4","key":"30_CR9","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N. Linial","year":"1990","unstructured":"Linial, N., Nisan, N.: Approximate inclusion-exclusion. Combinatorica\u00a010(4), 349\u2013365 (1990)","journal-title":"Combinatorica"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On \u03b5-biased generators in NC0. In: Proceedings of the 44th Annual Symposium on Foundations of Computer Science, pp. 136\u2013145 (2003)","DOI":"10.1109\/SFCS.2003.1238188"},{"issue":"1","key":"30_CR11","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02579445","volume":"5","author":"J.P. Schmidt","year":"1985","unstructured":"Schmidt, J.P., Shamir, E.: Component structure in the evolution of random hypergraphs. Combinatorica\u00a05(1), 81\u201394 (1985)","journal-title":"Combinatorica"},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.3233\/SAT190033","volume":"3","author":"D. Vilenchik","year":"2007","unstructured":"Vilenchik, D.: It\u2019s all about the support: a new perspective on the satisfiability problem. Journal on Satisfiability, Boolean Modeling, and Computation\u00a03, 125\u2013139 (2007)","journal-title":"Journal on Satisfiability, Boolean Modeling, and Computation"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:24:13Z","timestamp":1739305453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}