Archive for Октябрь 2010

Тестирование свойства «быть диктатором»

Октябрь 17, 2010

Этот пост является логическим продолжением поста про преобразование Фурье и тестирование линейности, так что лучше начать с него.

Пусть у нас есть булева функция f \colon \{-1, 1\}^n \to \{-1, 1\} (о том, почему мы используем плюс-минус единицы, можно прочитать в предыдущем посте). Назовем функцию диктатором, если f(x_1, \ldots, x_n) = x_i для некоторого i. Мы хотим запросить значение f в трех (!) точках, а потом сказать «да» или «нет» так, чтобы выполнялось два свойства:

  • Если f диктатор, то тест должен проходить с вероятностью близкой к единице.
  • Если тест проходит с вероятностью больше 1/2, то f близка к линейной функции с малым числом существенных переменных.

Напомню, что в первой части для проверки на линейность мы использовали тест f(x) \cdot f(y)=f(x \cdot y), где x, y \in \{-1, 1\}^n равномерно. В нашей ситуации он не подходит, так как тот факт, что он проходит с вероятностью больше 1/2, дает нам лишь близость к какой-то линейной функции, а нам нужна близость к линейной функции с малым числом существенных переменных. Таким образом, нужно как-то подредактировать тест.

Сделаем это очень странным образом. Возьмем случайный вектор z \in \{-1, 1\}^n, все z_i выбираем независимо, причем z_i = 1 с вероятностью 1 - \rho, а z_i = -1 с вероятностью \rho. Теперь тест будет выглядеть так: мы проверяем, что f(x) \cdot f(y) = f(x \cdot y \cdot z), где x и y по прежнему выбираются равномерно. То есть, мы по сути дела вносим слабый шум.

Проверим первое свойство нашего теста. Если f диктатор, то тест проходит тогда и только тогда, когда z_i = 1, что происходит с вероятностью 1 - \rho.

Теперь проверим второе свойство. Пусть мы знаем, что тест проходит с вероятностью 1/2 + \delta. Тогда E_{x,y,z} [f(x) \cdot f(y) \cdot f(x \cdot y \cdot z)] \geq 2 \delta. Теперь будем пользоваться преобразованием Фурье.

2 \delta \leq E_{x,y,z} [f(x) \cdot f(y) \cdot f(x \cdot y \cdot z)] =
= E_{x, y, z}[\sum_{\alpha, \beta, \gamma} \hat{f}_{\alpha}\hat{f}_{\beta}\hat{f}_{\gamma} \chi_{\alpha}(x) \chi_{\beta}(y) \chi_{\gamma}(x \cdot y \cdot z)] =
= \sum_{\alpha} \hat{f}_{\alpha}^3 E_{z} [\chi_{\alpha}(z)]

Так как компоненты z независимы, то несложно убедиться в том, что E_{z}[\chi_{\alpha}(z)] = (1 - 2 \rho)^{|\alpha|}. Итак, мы получаем, что

\sum_{\alpha} \hat{f}_{\alpha}^3 (1 - 2 \rho)^{|\alpha|} \geq 2 \delta. Заметьте, что наш искуственно созданный шум забивает члены этой суммы с большим |\alpha|, чего мы, собственно говоря, и добивались.

Из полученного соотношения несложно вывести, что для любого \varepsilon > 0 найдется коэффициент \hat{f}_{\alpha} с |\alpha| = O\left( \frac{1}{2 \rho} \log \frac{1}{\varepsilon} \right) такой, что \hat{f}_{\alpha} \geq 2 \delta - \varepsilon. То есть найдется линейная функция, которая (1/2 + \delta - \varepsilon / 2)-близка к f и которая зависит от O\left( \frac{1}{2 \rho} \log \frac{1}{\varepsilon} \right) переменных.

Эта конструкция применяется в доказательстве 3-битовой версии PCP теоремы.

Реклама