Теорема о списочном декодировании

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

Пусть $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_x(y) = h_x(y + r) + h_x(r)$$ Отсюда еще можно заметить, что если бы было испорчено не более четверти битов, то можно было $h_x(y), h_x(r)$ заменить на $\bar{h}$ и выбирать максимум. $$h_x(y) = \mathrm{majority}_r(\bar{h}(y + r) + h_x(r))$$ Можно взять выборку из попарно независимых $r_i$. Как их построить? Есть небольшое количество случайных вектор-строк длины $n$: $u_1, \ldots, u_s$.
$r_1, \ldots, r_{2^s - 1}$ - все нетривиальные суммы $u_j$. Они будут попарно независимыми равномерно распределенными. Представим $r_i$ в виде вектор-столбца $R = A \cdot U$.

$h_x(u_1 + u_2 + u_s) = h_x(u_1) + h_x(u_2) + h_x(u_s)$. То есть $h_x(r_i)$ полностью определяется $h_x(u_1), \ldots, h_x(u_s)$.

$k$-ый бит $x$: $x_k = h_k(e_k) = x \odot e_k$

Алгоритм восстановления $x$ (списком):

1. Для всех строк длины $b \in \{0, 1\}^s$

2. Для всех $k = 1, \ldots, n$
   $$x_k = \mathrm{majority}_{i = 1, \ldots, 2^s - 1}(\bar{h}(e_k + r_i) + h_x(r_i))$$ где $h_x(r_i)$ посчитан при условии $h_x(u_1) = b_1, \ldots, h_x(u_s) = b_s$

3. Добавить $x$ в список.

Введем случайные перменные $\xi_i$ - индикаторы $\bar{h}(y + r_i) = h_x(y + r_i)$. $r_i$ - случайные, следовательно $Pr\{\xi_i = 1\} \ge \frac{1}{2} + \varepsilon$. Посчитаем вероятность плохого исхода: $\le \frac{1}{4\varepsilon^2}\cdot\frac{1}{2^s - 1}\cdot n$. Хотим, чтобы последняя величина была меньше $\frac{1}{2}$. Откуда $s \simeq \log \frac{n}{\varepsilon^2}$. Весь алгоритм, как легко проверить, полиномиальный.