Вывод теоремы Голдрайха-Левина из теоремы о списочном декодировании

Теорема (Голдрайх-Левин)

Если $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^n$ - односторонняя перестановка, то $g: \{0, 1\}^{2n} \rightarrow \{0, 1\}^{2n}$, $g(x, y) = (f(x), y)$ - тоже односторонняя перестановка, а $h(x, y) = x \odot y$ - трудный бит для $g$.

Теорема (О кодах Адамара или о списочном декодировании)

Пусть $h_x(y) = x \odot y$ - код Адамара слова $x \in \{0, 1\}^n$. Пусть $\bar{h}(y)$ - такая функция, что доля $y$ удовлетоворяющих $\bar{h}(y) = h_x(y)$ больше либо равна $\frac{1}{2}$. Тогда существует вероятностный алгоритм, работающий $poly(\frac{n}{\varepsilon})$, имеющий произвольный доступ к $\bar{h}$, выдающий список слов длины $n$, с вероятностью $\ge \frac{1}{2}$ содержит $x$.

Почему это называется декодированием списка? Вообще кодирование нужно для исправления ошибок. Код Адамара - длинный код. Точного полиномиального алгоритма декодирования не существует. $h$ - код, $\bar{h}$ - испорченный код.

Теорема

Из теоремы о списочном декодировании выводится теорема Голдрайха-Левина.

Доказательство

Пусть существует схема, которая с вероятностью $\ge \frac{1}{2} + \varepsilon$ по $(f(x), y)$ находит $x \odot y$. $$Pr_y\{C(f(x), y) = x \odot y \} \ge \frac{1}{2} + \varepsilon$$ $$Pr_y\{\bar{C}(y) = h_x(y) \} \ge \frac{1}{2} + \varepsilon$$ $\bar{C}$ - искаженный код Адамара слова $x$.

Обратитель $f$:

1. Применяет алгоритм списочного декодирования для $\bar{h} = \bar{C}$ и $\varepsilon$.

2. Вычисляет значения $f$ на всех элементах полученного списка.

3. Если $f(\bar{x}) = f(x)$, то выводит $\bar{x}$, иначе выводит что угодно.

Утверждается, что этот обратитель будет достаточно успешным. Он точно будет работать полиномиальное время (он обращается к схеме, нужно переделать алгоритм в полиномиальную схему). Нужно понять, с какой вероятностью он будет обращать. Эта вероятность будет равна $\frac{\varepsilon}{4}$. Ибо если декодирование успешно, то нужный $x$ будет найден и вероятность успеха декодирования будет $\frac{1}{2}$. Нужно посчитать долю $x$, для которых $$Pr_y\{\bar{C}(y) = h_x(y)\} \ge \frac{1}{2} + \frac{\varepsilon}{2}$$ Эта доля $\ge \frac{\varepsilon}{2}$, иначе $$Pr_y\{C(f(x), y) = h_x(y)\} < \frac{\varepsilon}{2}\cdot 1 + 1\cdot(\frac{1}{2} + \frac{\varepsilon}{2}) = \frac{1}{2} + \varepsilon$$ Получили противоречие с предположением.

$\ge \frac{\varepsilon}{2}$ - вероятность хорошего $x$;

$\ge \frac{1}{2}$ - вероятность успешного обращения хорошего $x$

Из последних двух оценок поулчаем $\ge \frac{\varepsilon}{4}$ - вероятность успешного обращения $x$.