{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:01:36Z","timestamp":1759147296404},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,11,14]],"date-time":"2013-11-14T00:00:00Z","timestamp":1384387200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00224-013-9514-8","type":"journal-article","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T20:25:08Z","timestamp":1384287908000},"page":"261-276","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bound on Average-Case Complexity of Inversion of Goldreich\u2019s Function by Drunken Backtracking Algorithms"],"prefix":"10.1007","volume":"54","author":[{"given":"Dmitry","family":"Itsykson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,14]]},"reference":[{"key":"9514_CR1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/SFCS.2000.892064","volume-title":"FOCS\u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science","author":"M. Alekhnovich","year":"2000","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. In: FOCS\u201900: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 43. IEEE Comput. Soc., Washington (2000)"},{"issue":"1\u20133","key":"9514_CR2","first-page":"51","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. Reason. 35(1\u20133), 51\u201372 (2005)","journal-title":"J. Autom. Reason."},{"issue":"1","key":"9514_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s00037-011-0034-0","volume":"21","author":"A. Bogdanov","year":"2012","unstructured":"Bogdanov, A., Qiao, Y.: On the security of Goldreich\u2019s one-way function. Comput. Complex. 21(1), 83\u2013127 (2012)","journal-title":"Comput. Complex."},{"issue":"2","key":"9514_CR4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow\u2014resolution made simple. J. ACM 48(2), 149\u2013169 (2001)","journal-title":"J. ACM"},{"key":"9514_CR5","first-page":"521","volume-title":"Proceedings of TCC","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: Proceedings of TCC, pp. 521\u2013538 (2009)"},{"key":"9514_CR6","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: On the one-way function candidate proposed by Goldreich. Technical report 12-175, Electronic Colloquium on Computational Complexity (2012)"},{"key":"9514_CR7","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Commun. ACM 5, 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"key":"9514_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM 7, 201\u2013215 (1960)","journal-title":"J. ACM"},{"key":"9514_CR9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/11499107_5","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2005","unstructured":"E\u00e9n, N., Biere, A.: Effective preprocessing in SAT through variable and clause elimination. In: Theory and Applications of Satisfiability Testing, pp. 61\u201375 (2005)"},{"key":"9514_CR10","series-title":"Lecture Notes in Computer Science","first-page":"502","volume-title":"SAT","author":"N. Een","year":"2003","unstructured":"Een, N., Sorensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT. Lecture Notes in Computer Science, vol. 2919, pp. 502\u2013518 (2003)"},{"key":"9514_CR11","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. Technical report 00-090, Electronic Colloquium on Computational Complexity (2000)"},{"key":"9514_CR12","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43, 439\u2013561 (2006)","journal-title":"Bull. Am. Math. Soc."},{"key":"9514_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/978-3-642-25591-5_48","volume-title":"Algorithms and Computation\u201422nd International Symposium, ISAAC 2011","author":"D. Itsykson","year":"2011","unstructured":"Itsykson, D., Sokolov, D.: Lower bounds for myopic dpll algorithms with a cut heuristic. In: Algorithms and Computation\u201422nd International Symposium, ISAAC 2011. Lecture Notes in Computer Science, pp. 464\u2013473 (2011)"},{"key":"9514_CR14","first-page":"88","volume":"399","author":"D. Itsykson","year":"2012","unstructured":"Itsykson, D., Sokolov, D.: The complexity of inversion of explicit Goldreichs function by DPLL algorithms. Zap. Nau\u010dn. Semin. POMI 399, 88\u2013108 (2012)","journal-title":"Zap. Nau\u010dn. Semin. POMI"},{"key":"9514_CR15","doi-asserted-by":"crossref","unstructured":"Itsykson, D.: Lower bound on average-case complexity of inversion of Goldreich\u2019s function by drunken backtracking algorithms (in russian). Technical report 03\/2009, PDMI Preprint (2009)","DOI":"10.1007\/978-3-642-13182-0_19"},{"key":"9514_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/978-3-642-13182-0_19","volume-title":"Proceedings of 5th International Computer Science Symposium in Russia","author":"D. Itsykson","year":"2010","unstructured":"Itsykson, D.: Lower bound on average-case complexity of inversion of Goldreich function by drunken backtracking algorithms. In: Proceedings of 5th International Computer Science Symposium in Russia. Lecture Notes in Computer Science, vol. 6072, pp. 204\u2013215. Springer, Berlin (2010)"},{"key":"9514_CR17","unstructured":"Miller, R.: Goldreich\u2019s one-way function candidate and drunken backtracking algorithms. Master\u2019s thesis, University of Virginia (2009). Distinguished Majors Thesis"},{"key":"9514_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/11814948_13","volume-title":"Theory and Applications of Satisfiability Testing\u2014SAT 2006","author":"I. Mironov","year":"2006","unstructured":"Mironov, I., Zhang, L.: Applications of SAT solvers to cryptanalysis of hash functions. In: Biere, A., Gomes, C.P. (eds.) Theory and Applications of Satisfiability Testing\u2014SAT 2006. Lecture Notes in Computer Science, vol. 4121, pp. 102\u2013115 (2006)"},{"key":"9514_CR19","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. J. Comput. Syst. Sci. 49, 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9514_CR20","first-page":"234","volume":"8","author":"G.S. Tseitin","year":"1968","unstructured":"Tseitin, G.S.: On the complexity of derivation in the propositional calculus. Zap. Nau\u010d. Semin. POMI 8, 234\u2013259 (1968). English translation of this volume: Consultants Bureau, NY, pp. 115\u2013125 (1970)","journal-title":"Zap. Nau\u010d. Semin. POMI"},{"issue":"1","key":"9514_CR21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"Urquhart, A.: Hard examples for resolution. J. ACM 34(1), 209\u2013219 (1987)","journal-title":"J. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9514-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9514-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9514-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T13:26:11Z","timestamp":1564665971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9514-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,14]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9514"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9514-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,14]]}}}