Все ли функции, вес Фурье которых сконцентрирован на множествах малого размера, вычисляются цепями AC0?

Все ли функции, чей вес Фурье сконцентрирован на множествах малого размера (или членах с низкой степенью), вычисляются по схемам ? $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
источник

Этот вопрос звучит интересно, хотя мне не хватает некоторого фона в анализе Фурье. Буду признателен за ссылки на соответствующую литературу.

Маркус

@Markus: эта книга 2.0 Райана О'Доннелла является отличным справочником: contrib.andrew.cmu.edu/~ryanod

Алессандро

почти обратная связь с линиалом, мансуром, ниссаном 1993 года ? результат Ааронсона, контрпример к обобщенному линиалу-ниссану кажется близким? но имхо, должен быть способ как-то обобщить результат 1993 года ... может быть, в широком смысле ...

vzn

другая аналогичная идея вместо AC ^ 0, которую сложнее опровергнуть, заключалась бы в неограниченной глубине, но ограниченных цепями затворов, ограниченных некоторой «маленькой» функцией, скажем, полиномиальной и т. д.? Кроме того, связь между монотонными цепями и коэффициентами Фурье не так хорошо известна ...?

vzn

см. также полилогарифмическая независимость, дураки схемы AC ^ 0 от Braverman

vzn

Ответы:

Рассмотрим следующую функцию на : $\{0,1\}^n$ Очевидно, что эта функция сложна для AC⁰. С другой стороны, функция почти постоянна, поэтому почти весь ее спектр Фурье находится на первом уровне.

f (x) = x_{0} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1}) .

$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$

Если вы хотите сбалансированный контрпример, рассмотрим

g (x) = x_{0} \oplus [x_{1} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1})] .

$g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1})\right].$

x_{0}

$x_0$

Юваль Фильмус
источник

У вас есть надежные примеры, когда функция не может быть аппроксимирована в AC0?

MCH

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

A C^{0}

$AC^0$

@Arul Уровень Фурье состоит из всех коэффициентов Фурье, соответствующих наборам заданного размера. Мы думаем о них как в порядке возрастания размера. Что касается того, почему эта функция трудна для AC0, это упражнение. Подсказка: паритет сложен для AC0.

Юваль Фильмус

Есть несколько способов понять вопрос в соответствии с точным значением «маленький размер» и «сосредоточиться».

$1-o(1)$ $S$ $1-o(1)$ ${\rm AC^0}$ .

2) Существует теорема Бургейна о том, что если концентрация значительно выше концентрации мажоритарной функции, то эта функция приблизительно равна хунте и, таким образом, зависит от O (1) переменных.

$\hat f^2(S)$ $AC^0$ ${\rm polylog} (n)$ . Если суммарное влияние равно O (1), то функция близка к хунте, а именно зависит от O (1) переменных.

$O(\log n)$ $AC^0$ .

$O(polylog (n))$ $n^{polylog (n)}$

Гил Калай
источник