DOI

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.

Язык оригиналаанглийский
Страницы (с-по)47-58
Число страниц12
ЖурналJournal of Mathematical Sciences (United States)
Том188
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2013

    Предметные области Scopus

  • Теория вероятности и статистика
  • Математика (все)
  • Прикладная математика

ID: 49786184