Research output: Contribution to journal › Article › peer-review
The complexity of inverting explicit Goldreich's function by DPLL algorithms. / Itsykson, D. M.; Sokolov, D. O.
In: Journal of Mathematical Sciences (United States), Vol. 188, No. 1, 01.01.2013, p. 47-58.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - The complexity of inverting explicit Goldreich's function by DPLL algorithms
AU - Itsykson, D. M.
AU - Sokolov, D. O.
PY - 2013/1/1
Y1 - 2013/1/1
N2 - Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by a fixed predicate of arity d. Every Goldreich's function is determined by its dependency graph G and a predicate P. In 2000, O. Goldreich formulated the 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 an exponential lower bound on the inversion of Goldreich's function by myopix DPLL algorithms. The dependency graph G in our construction may be based on an arbitrary expander; in particular, one can use an explicit expander; while all previously known results are based on random dependency graphs. The predicate P can be linear or slightly nonlinear. Our construction can be used in the proof of lower bounds for drunken DPLL algorithms as well. Bibliography: 18 titles.
AB - Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by a fixed predicate of arity d. Every Goldreich's function is determined by its dependency graph G and a predicate P. In 2000, O. Goldreich formulated the 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 an exponential lower bound on the inversion of Goldreich's function by myopix DPLL algorithms. The dependency graph G in our construction may be based on an arbitrary expander; in particular, one can use an explicit expander; while all previously known results are based on random dependency graphs. The predicate P can be linear or slightly nonlinear. Our construction can be used in the proof of lower bounds for drunken DPLL algorithms as well. Bibliography: 18 titles.
UR - http://www.scopus.com/inward/record.url?scp=84871933216&partnerID=8YFLogxK
U2 - 10.1007/s10958-012-1105-8
DO - 10.1007/s10958-012-1105-8
M3 - Article
AN - SCOPUS:84871933216
VL - 188
SP - 47
EP - 58
JO - Journal of Mathematical Sciences
JF - Journal of Mathematical Sciences
SN - 1072-3374
IS - 1
ER -
ID: 49786184