Дурачить произвольные симметричные функции

17

Распределение называется ϵ- обмануть функцию f, если | E x U ( f ( x ) ) - E x D ( f ( x ) ) | ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе. Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см. Алон-Гольдрайх-Хастад-ПеральтаDϵf|ExU(f(x))ExD(f(x))|ϵ

ϵдля некоторых хороших конструкций таких пространств). Вопрос, который я хочу задать, является обобщением этого вопроса на произвольные симметричные функции.

Вопрос: Предположим, что мы берем класс произвольных симметрических функций над некоторым подмножеством, есть ли у нас распределение (с небольшой поддержкой), которое обманывает этот класс?

Несколько небольших наблюдений:

  • Достаточно обмануть точные пороговые значения ( равно 1 тогда и только тогда, когда x имеет ровно k единиц среди индексов в S ). Любое распределение , что ε -fools эти точные пороги будут п ε обмануть все симметричные функции над п битами. (Это потому, что каждая симметричная функция может быть записана как реальная линейная комбинация этих точных пороговых значений, где коэффициенты в комбинации равны либо 0, либо 1. Линейность ожидания дает нам то, что мы хотим) Аналогичный аргумент также работает для общих порогов ( Th S k ( xEThkS(x)xkSϵnϵn

    равен 1 тогда и только тогда, когда x имеет хотя бы k единиц среди индексов в S )ThkS(x)xkS

  • Существует явное построение дистрибутива с поддержкой через PRG Нисана для LOGSPACE .nO(logn)

  • Произвольное -biased пространства не будет работать. Например, если S - это множество всех x, таких что число единиц в x не равно нулю mod 3, это на самом деле ϵ- смещено для очень малых ϵ (из результата Аркадьева Чаттопадяй ). Но ясно, что это не обманывает функцию MOD3.ϵSxϵϵ

Интересная подзадача может быть следующей: предположим, что мы просто хотим обмануть симметричные функции по всем n индексам , у нас есть хорошее пространство? Согласно вышеприведенным наблюдениям, нам просто нужно обмануть пороговые функции по битам, которые являются просто семейством n + 1 функций. Таким образом, можно просто выбрать распределение грубой силой. Но есть ли более хорошие примеры пространств, которые обманывают Th [ n ] k для каждого k ?nn+1Thk[n]k

Ramprasad
источник
Может быть, этот комментарий может помочь. Гипотеза Линиала и Нисана была недавно решена Марком Браверманом. Название статьи: «Полилогарифмическая независимость дураков цепей AC ^ 0». cs.toronto.edu/~mbraverm/Papers/FoolAC0v7.pdf
Мирмойтаба Гариби,

Ответы:

11

Да, общее решение этой проблемы недавно было дано Парикшитом Гопаланом, Рагу Мека, Омером Рейнгольдом и Дэвидом Цукерманом, см. Псевдослучайные генераторы для комбинаторных форм .

Этот документ обрабатывает еще более общую настройку, когда генератор выводит log m- битных блоков, которые затем передаются в произвольные булевы функции, чьи n выходов затем передаются в булеву симметричную функцию.n logmn

Различные подслучаи уже были известны; см., например, генераторы псевдослучайных битов, которые обманывают модульные суммы , ограниченные независимые дураки полупространства и генераторы псевдослучайных значений для полиномиальных пороговых функций . Первые ручки сумм по модулю . Второй и третий обрабатывают именно те пороговые тесты, о которых вы упомянули, однако ошибка недостаточно хороша, чтобы применить ваши рассуждения для получения результата для каждой симметричной функции.p

Manu
источник
1
Но Гопалан-Мека-Рейнгольд-Цукерман не дают оптимального PRG для обратной полиномиальной ошибки, верно? Для константы это оптимально. Тем не менее, большое спасибо за указатель. ε
Рампрасад
На самом деле они этого не делают. В общем, это трудная цель, и в литературе относительно мало случаев, когда достигается логарифмическая зависимость от . ϵ
Ману