Распределение называется ϵ- обмануть функцию f, если | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе.
Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см. Алон-Гольдрайх-Хастад-Перальта
для некоторых хороших конструкций таких пространств). Вопрос, который я хочу задать, является обобщением этого вопроса на произвольные симметричные функции.
Вопрос: Предположим, что мы берем класс произвольных симметрических функций над некоторым подмножеством, есть ли у нас распределение (с небольшой поддержкой), которое обманывает этот класс?
Несколько небольших наблюдений:
Достаточно обмануть точные пороговые значения ( равно 1 тогда и только тогда, когда x имеет ровно k единиц среди индексов в S ). Любое распределение , что ε -fools эти точные пороги будут п ε обмануть все симметричные функции над п битами. (Это потому, что каждая симметричная функция может быть записана как реальная линейная комбинация этих точных пороговых значений, где коэффициенты в комбинации равны либо 0, либо 1. Линейность ожидания дает нам то, что мы хотим) Аналогичный аргумент также работает для общих порогов ( Th S k ( x
равен 1 тогда и только тогда, когда x имеет хотя бы k единиц среди индексов в S )Существует явное построение дистрибутива с поддержкой через PRG Нисана для LOGSPACE .
Произвольное -biased пространства не будет работать. Например, если S - это множество всех x, таких что число единиц в x не равно нулю mod 3, это на самом деле ϵ- смещено для очень малых ϵ (из результата Аркадьева Чаттопадяй ). Но ясно, что это не обманывает функцию MOD3.
Интересная подзадача может быть следующей: предположим, что мы просто хотим обмануть симметричные функции по всем n индексам , у нас есть хорошее пространство? Согласно вышеприведенным наблюдениям, нам просто нужно обмануть пороговые функции по битам, которые являются просто семейством n + 1 функций. Таким образом, можно просто выбрать распределение грубой силой. Но есть ли более хорошие примеры пространств, которые обманывают Th [ n ] k для каждого k ?
Ответы:
Да, общее решение этой проблемы недавно было дано Парикшитом Гопаланом, Рагу Мека, Омером Рейнгольдом и Дэвидом Цукерманом, см. Псевдослучайные генераторы для комбинаторных форм .
Этот документ обрабатывает еще более общую настройку, когда генератор выводит log m- битных блоков, которые затем передаются в произвольные булевы функции, чьи n выходов затем передаются в булеву симметричную функцию.n logm n
Различные подслучаи уже были известны; см., например, генераторы псевдослучайных битов, которые обманывают модульные суммы , ограниченные независимые дураки полупространства и генераторы псевдослучайных значений для полиномиальных пороговых функций . Первые ручки сумм по модулю . Второй и третий обрабатывают именно те пороговые тесты, о которых вы упомянули, однако ошибка недостаточно хороша, чтобы применить ваши рассуждения для получения результата для каждой симметричной функции.p
источник