The complexity of inversion of explicit Goldreich's function by DPLL algorithms

D. M. Itsykson ; D. O. Sokolov

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 88-108

Résumé

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.