TY - GEN

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

AU - Itsykson, Dmitry

AU - Sokolov, Dmitry

PY - 2011/6/23

Y1 - 2011/6/23

N2 - 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 2005 M. Alekhnovich, E. Hirsch and D. Itsykson proved the exponential lower bound on the complexity of inversion of Goldreich's function based on linear predicate and random graph by myopic DPLL agorithms. In 2009 J. Cook, O. Etesami, R. Miller, and L. Trevisan extended this result to nonliniar predicates (but for a slightly weaker definition of myopic algorithms). Recently D. Itsykson and independently R. Miller proved the lower bound for drunken DPLL algorithms that invert Goldreich's function with nonlinear P and random G. All above lower bounds are randomized. The main contribution of this paper is the simpler proof of the exponential lower bound of the Goldreich's function inversion by myopic DPLL algorithms. A dependency graph in our construction may be based on an arbitrary expander, particulary it is possible to use an explicit expander; the predicate may be linear or slightly nonlinear. Our definition of myopic algorithms is more general than one used by J. Cook et al. Our construction may be used in the proof of lower bound for drunken algorithms as well.

AB - 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 2005 M. Alekhnovich, E. Hirsch and D. Itsykson proved the exponential lower bound on the complexity of inversion of Goldreich's function based on linear predicate and random graph by myopic DPLL agorithms. In 2009 J. Cook, O. Etesami, R. Miller, and L. Trevisan extended this result to nonliniar predicates (but for a slightly weaker definition of myopic algorithms). Recently D. Itsykson and independently R. Miller proved the lower bound for drunken DPLL algorithms that invert Goldreich's function with nonlinear P and random G. All above lower bounds are randomized. The main contribution of this paper is the simpler proof of the exponential lower bound of the Goldreich's function inversion by myopic DPLL algorithms. A dependency graph in our construction may be based on an arbitrary expander, particulary it is possible to use an explicit expander; the predicate may be linear or slightly nonlinear. Our definition of myopic algorithms is more general than one used by J. Cook et al. Our construction may be used in the proof of lower bound for drunken algorithms as well.

KW - DPLL algorithm

KW - expander

KW - lower bounds

KW - one-way function

UR - http://www.scopus.com/inward/record.url?scp=79959296171&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20712-9_11

DO - 10.1007/978-3-642-20712-9_11

M3 - Conference contribution

AN - SCOPUS:79959296171

SN - 9783642207112

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 134

EP - 147

BT - Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, Proceedings

T2 - 6th International Computer Science Symposium in Russia, CSR 2011

Y2 - 14 June 2011 through 18 June 2011

ER -