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 languageEnglish
Pages (from-to)47-58
Number of pages12
JournalJournal of Mathematical Sciences (United States)
Volume188
Issue number1
DOIs
StatePublished - 1 Jan 2013

    Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Applied Mathematics

ID: 49786184