Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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 |
ID: 49786184