Булевы функции коэффициентов Фурье, описываемые схемами с ограниченной глубиной с вентилями AND OR и XOR

29

Пусть - булева функция, и давайте подумаем о f как о функции от до . На этом языке разложение Фурье функции f является просто разложением функции f по квадратным свободным мономам. (Эти мономов образуют базис для пространства вещественных функций на . Сумма квадратов коэффициентов равна просто так что приводит к распределению вероятностей по квадратным свободным мономам. Назовем это распределение F-распределением.f{1,1}n{1,1}2n{1,1}n1f

Если f можно описать ограниченным контуром глубины полиномиального размера, то из теоремы Линиала, Мансура и Нисана мы знаем, что распределение F сосредоточено на размером вплоть до почти экспоненциально малого веса. Это вытекает из леммы переключения Hastad. (Прямое доказательство было бы наиболее желательно.)polylog n

Что происходит, когда мы добавляем врата мод 2? Одним из примеров для рассмотрения является функция для переменных, которая описывается как внутреннее произведение mod 2 первых n переменных и последних n переменных. Здесь F-распределение равномерно.IP2n2n

Вопрос : F-распределение булевой функции, описываемой ограниченным полиномиальным размером размера AND, OR, MOD , сосредоточено (с точностью до сверхполиномиально малой ошибки) на «уровнях»?2o(n)

Замечания :

  1. Одним из возможных путей к контрпримеру было бы «склеить» различные IP на непересекающихся наборах переменных, но я не вижу, как это сделать. Возможно, следует ослабить вопрос и разрешить присваивать переменные некоторым весам, но я также не вижу четкого способа сделать это. (Таким образом, ссылка на эти два вопроса также является частью того, о чем я спрашиваю.)2k

  2. Я бы предположил, что положительный ответ на вопрос (или к успешному варианту) будет применяться также и тогда, когда вы разрешите моду . (Таким образом, постановка вопроса была мотивирована недавним впечатляющим результатом ACC Райана Уильямса.) k

  3. Для MAJORITY F-распределение велико (1 / poly) для каждого «уровня».

Как показал Лука, ответ на заданный мной вопрос - «нет». Вопрос, который остается, состоит в том, чтобы предложить способы поиска свойств F-распределений булевых функций, которые могут быть описаны с помощью логических элементов AND OR и mod 2, которые не являются общими для MAJORITY.

Попытка сохранить вопрос, рассказав о функциях MONOTONE:

Вопрос : F-распределение булевой функции MONOTONE, описываемой полиномиальным размером с ограниченной глубиной, AND, OR, MOD , сконцентрировано (с точностью до сверхполиномиально малой ошибки) на «уровнях»?2o(n)

Мы можем предположить, что мы можем даже заменить на так что контрпример для этой сильной версии может быть интересным. o(n)polylog(n)

Гил Калай
источник
Это кажется очень сильным предположением, было бы очень интересно, если бы были доказательства, что это может быть правдой. Неужели за этим стоит интуиция, что для контуров постоянной глубины с модулями у вас могут быть функции, которые очень нечувствительны к шуму, такие как полиномы низкой степени, или совершенно случайные, как четность, но трудно создать что-то в середине, как большинство?
Вооз Барак
Уважаемый Вооз, (я бы ожидал контрпример к сильному предложенному утверждению.) Re: интуиция, замените «совершенно случайный» на «подобный Бернулли». Насколько я помню, когда вы рассматриваете один вентиль mod k, то F-распределение похоже на определенное распределение Бернулли (а именно, вес для | S | подобен p ^ | S | (1-p) ^ {n- | S | } для некоторого p, не обязательно p = 1 / 2. Таким образом, похоже, что схемы с малой ограниченной глубиной с затворами mod k манипулируют своими F-распределениями, такими как распределения Бернулли, так что, возможно, свойство "большинства весов на нескольких уровнях" (или некоторые другие собственность распределений Бернулли)
Gil Kalai

Ответы:

31

Гил, что-нибудь вроде этого будет контрпримером?

Пусть таково, что , и представьте, что битный вход - это пара где - это m-битная строка а - целое число. в диапазоне записано в двоичном виде.mn=m+logmn(x,i)x(x1,,xm)i1,,m

Затем мы определяемf(x,i):=x1xi

Теперь для каждого функция f () имеет соотношение с символом Фурье , и, таким образом, «уровень i» имеет по крайней мере доля масс. (На самом деле больше, но этого должно хватить)i=1,,m1/mx1xi1/m2

f () может быть реализовано в глубине-3: поместите все XOR в слой, а затем выполните «выделение» в двух слоях AND, OR и NOT (не считая NOT как добавление к глубине, как обычно).

Лука Тревизан
источник
да, Лука, похоже, ты прав.
Гил Калай