|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 399, Pages 88–108
(Mi znsl5222)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
D. M. Itsykson, D. O. Sokolov St. Petersburg Department of the Steklov Mathematical
Institute, St. Petersburg, Russia
Abstract:
The Goldreich's function has $n$ binary inputs and $n$ binary outputs. Every output depends on $d$ inputs and is computed from them by the fixed predicate of arity $d$. Every Goldreich's function is defined by it's dependency graph $G$ and predicate $P$. In 2000 O. Goldreich formulated a 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 the exponential lower bound of the Goldreich's function inversion by myopic DPLL algorithms. A dependency graph $G$ in our construction may be based on an arbitrary expander, particulary it is possible to use an explicit expander; while all all previously known results are based on random dependency graphs. The predicate $P$ may be linear or slightly nonlinear. Our construction may be used in the proof of lower bounds for drunken DPLL algorithms as well.
Key words and phrases:
DPLL algorithm, expander, one-way function, lower bounds.
Received: 31.07.2011
Citation:
D. M. Itsykson, D. O. Sokolov, “The complexity of inversion of explicit Goldreich's function by DPLL algorithms”, Computational complexity theory. Part X, Zap. Nauchn. Sem. POMI, 399, POMI, St. Petersburg, 2012, 88–108; J. Math. Sci. (N. Y.), 188:1 (2013), 47–58
Linking options:
https://www.mathnet.ru/eng/znsl5222 https://www.mathnet.ru/eng/znsl/v399/p88
|
Statistics & downloads: |
Abstract page: | 241 | Full-text PDF : | 50 | References: | 37 |
|