Случайные функции низкой степени как вещественный полином

Есть ли (разумный) способ выбрать равномерно случайную булеву функцию , степень которой как вещественный полином не превосходит ?$f:\{0,1\}^n \to \{0,1\}$$d$

РЕДАКТИРОВАТЬ: Нисан и Сегеди показали, что функция степени зависит не более чем от координат, поэтому мы можем предположить, что . Проблемы, как я вижу, следующие: 1) С одной стороны, если мы выберем случайную булеву функцию для координат , то ее степень будет близка к , намного выше, чем . 2) С другой стороны, если мы выберем каждый коэффициент степени не более случайным образом, то функция не будет булевой.$d$$d2^d$$n \leq d2^d$$d2^d$$d2^d$$d$$d$

Таким образом, вопрос заключается в следующем: есть ли способ выборки логической функции низкой степени, которая позволяет избежать этих двух проблем?

Вот алгоритм, который побеждает тривиальные попытки.

Следующее является известным фактом (упражнение 1.12 в книге О'Доннелла): если $f:\{-1,1\}^n\to\{-1,1\}$ - булева функция, у которой степень $\le d$ является полиномом, то каждый коэффициент Фурье из $f$ , F ( S ) представляет собой целое число , кратное 2 - d . Используя Коши-Шварца и Парсеваля, получаем, что существует не более 4 d ненулевых коэффициентов Фурье и ∑ S | $\hat{f}(S)$$2^{-d}$$4^d$$\sum_{S}{|\hat{f}(S)|}\le 2^{d}$.

Это предполагает метод выборки -

1. Выберите случайные неотрицательные целые числа $a_S$ для всех множеств $S\subseteq[n]$ размера не более $d$ , сумма которых до $\le 4^d$ .
2. Пусть $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$.
3. Убедитесь, что $f$ логическое. Если так, верните $f$ . Иначе вернитесь к $1$ .

Обратите внимание, что для каждой степени $\le d$ полинома $f$ точно один выбор случайных целых чисел на шаге 1 сгенерирует полином $f$ . Вероятность получения определенной степени $\le d$ полинома равна

Осталось показать, как выполнить шаг 3. Можно определить $A = \bigcup\{S:a_S\neq 0\}$ . Проверьте это $|A| \le d 2^d$ (который следует проводить с помощью нисан-Szegedy для каждой булевой функции) , а затем оценить $f$ на все возможные присвоения переменных в $A$ . Это можно сделать вовремя $2^{d 2^d}$ . Гур и Тамуз предлагают гораздо более быстрый рандомизированный алгоритм для этой задачи, однако, поскольку эта часть не доминирует во временной сложности, этого достаточно.

В целом алгоритм выдает случайную выборку степени $\le d$ полинома во времени $O(\frac{n}{d})^{d4^d}$. В предположении, что$n \le d2^d$временная сложность составляет$2^{O(d^2 4^d)}$.

Это не полиномиальное время выборки алгоритма, хотя он гораздо быстрее , чем выборка совершенно случайная функции (в этом случае вероятность получения степени специфического $\le d$ полином $1/2^{2^n}$ ).