Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 08/2010

СЛОЖНОСТЬ ОБРАЩЕНИЯ ЯВНОЙ ФУНКЦИИ ГОЛДРЕЙХА DPLL АЛГОРИТМАМИ

This preprint was accepted October 25, 2010

АННОТАЦИЯ:
Рассмотрим функцию $g: \{0,1\}^n \to \{0,1\}^n$, в которой каждый 
бит выхода зависит от $d$ битов входа и вычисляется 
по некоторому предикату. В 2000 году О. Голдрейх выдвинул гипотезу, 
что если граф зависимости является экспандером, 
а предикат случайный, то такая функция является односторонней. 
В 2005 году М. Алехновичем, Э.А. Гиршем и Д. Ицыксоном 
была доказана экспоненциальная нижняя оценка на сложность 
обращения функции Голдрейха, основанной на случайном графе 
и линейном предикате, близорукими алгоритмами расщепления. 
В 2009 году Дж. Кук, Р. Миллер, О. Этесами и Л. Тревисан обобщили этот 
результат на нелинейный предикат, немного ослабив возможности 
близоруких противников. Д. Ицыксон в 2010 году доказал нижнюю оценку на сложность 
обращения таких функций ``пьяными'' алгоритмами, 
основанными на расщеплении. Во всех перечисленных результатах нижняя оценка~--- вероятностная и 
достигается на случайном графе. Мы предлагаем явную конструкцию 
нелинейной функции Голдрейха, 
на которой достигаются все перечисленные оценки. Мы считаем, что
среди таких функций действительно есть труднообратимая. 
Мы приводим более простое доказательство нижней оценки для 
близоруких алгоритмов (в определениях [AHI05], которое более общее,
чем то, которое использовалось в [CEMT09]).
©

D.M. Itsykson, D.O. Sokolov

THE COMPLEXITY OF INVERSION OF EXPLICIT GOLDREICH'S FUNCTION BY PDLL ALGORITHMS

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 2005 M. Alekhnovich, E. Hirsch and D. Itsykson proved the exponential 
lower bound on the complexity of inversion of Goldreich's function 
based on linear predicate and random graph by myopic DPLL 
agorithms. In 2009 J. Cook, O. Etesami, R. Miller, and L. Trevisan 
extended this result to nonliniar predicates
(but for a slightly weaker definition of myopic algorithms). 
In 2010 D. Itsykson proved the lower bound for drunken DPLL algorithms 
that invert Goldreich's function with nonlinear $P$ and random $G$. 
All above lower bounds are randomized.
We show how to prove the explicit lower bound based on explicit expanders.
Moreover we give a simpler proof of the exponential lower bound 
for myopic algorithms. Our definition of myopic algorithms
is more general than one used by J. Cook et al.