Research output: Contribution to journal › Article › peer-review
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.
Original language | English |
---|---|
Pages (from-to) | 47-58 |
Number of pages | 12 |
Journal | Journal of Mathematical Sciences (United States) |
Volume | 188 |
Issue number | 1 |
DOIs | |
State | Published - 1 Jan 2013 |
ID: 49786184