Geodesic
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 88-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The Goldreich's function has $n$ binary inputs and $n$ binary outputs. Every output depends on $d$ inputs and is computed from them by the fixed predicate of arity $d$. Every Goldreich's function is defined by it's dependency graph $G$ and predicate $P$. In 2000 O. Goldreich formulated a conjecture that if $G$ is an expander and $P$ is a random predicate of arity $d$ then the corresponding function is one way. In this paper we give a simple proof of the exponential lower bound of the Goldreich's function inversion by myopic DPLL algorithms. A dependency graph $G$ in our construction may be based on an arbitrary expander, particulary it is possible to use an explicit expander; while all all previously known results are based on random dependency graphs. The predicate $P$ may be linear or slightly nonlinear. Our construction may be used in the proof of lower bounds for drunken DPLL algorithms as well. 
@article{ZNSL_2012_399_a4,
     author = {D. M. Itsykson and D. O. Sokolov},
     title = {The complexity of inversion of explicit {Goldreich's} function by {DPLL} algorithms},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {88--108},
     year = {2012},
     volume = {399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a4/}
}
TY  - JOUR
AU  - D. M. Itsykson
AU  - D. O. Sokolov
TI  - The complexity of inversion of explicit Goldreich's function by DPLL algorithms
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 88
EP  - 108
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a4/
LA  - en
ID  - ZNSL_2012_399_a4
ER  - 
%0 Journal Article
%A D. M. Itsykson
%A D. O. Sokolov
%T The complexity of inversion of explicit Goldreich's function by DPLL algorithms
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 88-108
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a4/
%G en
%F ZNSL_2012_399_a4
D. M. Itsykson; D. O. Sokolov. The complexity of inversion of explicit Goldreich's function by DPLL algorithms. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 88-108. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a4/

[1] J. Cook, O. Etesami, R. Miller, L. Trevisan, “Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms”, Proceedings of TCC, Springer-Verlag, 2009, 521–538 | MR | Zbl

[2] M. Alekhnovich, E. A. Hirsch, A. Edward, D. Itsykson, “Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas”, J. Autom. Reason., 35:1–3 (2005), 51–72 | MR | Zbl

[3] L. Levin, “One-way functions and pseudorandom generators”, Combinatorica, 7:4 (1987), 357–363 | DOI | MR | Zbl

[4] O. Goldreich, “Candidate One-Way Functions Based on Expander Graphs”, Electronic Colloquium on Computational Complexity, 2000, 00-090

[5] E. Ben-Sasson, A. Wigderson, “Short proofs are narrow – resolution made simple”, J. ACM, 48:2 (2001), 149–169 | DOI | MR | Zbl

[6] S. Hoory, N. Linial, A. Wigderson, “Expander graphs and their applications”, Bull. Amer. Math. Soc., 43 (2006), 439–561 | DOI | MR | Zbl

[7] N. Nisan, A. Wigderson, “Hardness vs. randomness”, J. Computer System Sciences, 49 (1994), 149–167 | DOI | MR | Zbl

[8] I. Mironov, L. Zhang, “Applications of SAT Solvers to Cryptanalysis of Hash Functions”, Theory and Applications of Satisfiability Testing – SAT, Lect. Notes Comput. Sci., 4121, eds. A. Biere, C. P. Gomes, Springer, 2006, 102–115 | DOI | MR | Zbl

[9] G. S. Tseitin, “On the complexity of derivation in the propositional calculus”, Zap. Nauchn. Semin. LOMI, 8, 1968, 234–259 | MR | Zbl

[10] N. Eén, A. Biere, “Effective Preprocessing in SAT Through Variable and Clause Elimination”, Theory and Applications of Satisfiability Testing, 2005, 61–75 | DOI | MR | Zbl

[11] N. Een, N. Sorensson, “An Extensible SAT-solver”, SAT 2003, Lect. Notes Computer Science, 2919, Springer, 2004, 502–518 | DOI | Zbl

[12] M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, A. Wigderson, “Pseudorandom generators in propositional proof complexity”, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 2000, 43 | DOI | MR

[13] A. Urquhart, “Hard Examples for Resolution”, JACM, 34:1 (1987), 209–219 | DOI | MR | Zbl

[14] M. Davis, G. Logemann, D. Loveland, “A machine program for theorem-proving”, Communications ACM, 5 (1962), 394–397 | DOI | MR | Zbl

[15] M. Davis, H. Putnam, “A computing procedure for quantification theory”, JACM, 7 (1960), 201–215 | DOI | MR | Zbl

[16] M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson, “Randomness conductors and constant-degree lossless expanders”, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, 659–668 | MR | Zbl

[17] D. Itsykson, “Lower bound on average-case complexity of inversion of Goldreich function by drunken backtracking algorithms”, Proceedings of International Computer Science Symposium in Russia, Lecture Notes in Computer Science, Springer, 2010, 204–215 | DOI | MR | Zbl

[18] R. Miller, Goldreich's one-way function candidate and drunken backtracking algorithms, University of Virginia, 2009