Пусть - булева функция, и давайте подумаем о f как о функции от до . На этом языке разложение Фурье функции f является просто разложением функции f по квадратным свободным мономам. (Эти мономов образуют базис для пространства вещественных функций на . Сумма квадратов коэффициентов равна просто так что приводит к распределению вероятностей по квадратным свободным мономам. Назовем это распределение F-распределением.
Если f можно описать ограниченным контуром глубины полиномиального размера, то из теоремы Линиала, Мансура и Нисана мы знаем, что распределение F сосредоточено на размером вплоть до почти экспоненциально малого веса. Это вытекает из леммы переключения Hastad. (Прямое доказательство было бы наиболее желательно.)
Что происходит, когда мы добавляем врата мод 2? Одним из примеров для рассмотрения является функция для переменных, которая описывается как внутреннее произведение mod 2 первых n переменных и последних n переменных. Здесь F-распределение равномерно.
Вопрос : F-распределение булевой функции, описываемой ограниченным полиномиальным размером размера AND, OR, MOD , сосредоточено (с точностью до сверхполиномиально малой ошибки) на «уровнях»?
Замечания :
Одним из возможных путей к контрпримеру было бы «склеить» различные IP на непересекающихся наборах переменных, но я не вижу, как это сделать. Возможно, следует ослабить вопрос и разрешить присваивать переменные некоторым весам, но я также не вижу четкого способа сделать это. (Таким образом, ссылка на эти два вопроса также является частью того, о чем я спрашиваю.)
Я бы предположил, что положительный ответ на вопрос (или к успешному варианту) будет применяться также и тогда, когда вы разрешите моду . (Таким образом, постановка вопроса была мотивирована недавним впечатляющим результатом ACC Райана Уильямса.)
Для MAJORITY F-распределение велико (1 / poly) для каждого «уровня».
Как показал Лука, ответ на заданный мной вопрос - «нет». Вопрос, который остается, состоит в том, чтобы предложить способы поиска свойств F-распределений булевых функций, которые могут быть описаны с помощью логических элементов AND OR и mod 2, которые не являются общими для MAJORITY.
Попытка сохранить вопрос, рассказав о функциях MONOTONE:
Вопрос : F-распределение булевой функции MONOTONE, описываемой полиномиальным размером с ограниченной глубиной, AND, OR, MOD , сконцентрировано (с точностью до сверхполиномиально малой ошибки) на «уровнях»?
Мы можем предположить, что мы можем даже заменить на так что контрпример для этой сильной версии может быть интересным.
Ответы:
Гил, что-нибудь вроде этого будет контрпримером?
Пусть таково, что , и представьте, что битный вход - это пара где - это m-битная строка а - целое число. в диапазоне записано в двоичном виде.m n=m+logm n (x,i) x (x1,…,xm) i 1,…,m
Затем мы определяемf(x,i):=x1⊕⋯⊕xi
Теперь для каждого функция f () имеет соотношение с символом Фурье , и, таким образом, «уровень i» имеет по крайней мере доля масс. (На самом деле больше, но этого должно хватить)i=1,…,m 1/m x1⊕⋯⊕xi 1/m2
f () может быть реализовано в глубине-3: поместите все XOR в слой, а затем выполните «выделение» в двух слоях AND, OR и NOT (не считая NOT как добавление к глубине, как обычно).
источник