Losowe funkcje niskiego stopnia jako prawdziwy wielomian

Czy istnieje (rozsądny) sposób na pobranie próbki losowo jednakowej funkcji boolowskiej której stopień rzeczywistej wielomianu wynosi co najwyżej ? $f:\{0,1\}^n \to \{0,1\}$ $d$

EDYCJA: Nisan i Szegedy wykazali, że funkcja stopnia zależy od co najwyżej współrzędnych , więc możemy założyć, że . Problemy, które widzę, są następujące: 1) Z jednej strony, jeśli wybierzemy losową funkcję logiczną na współrzędnych , to jej stopień będzie zbliżony do , znacznie wyższy niż . 2) Z drugiej strony, jeśli wybieramy każdy współczynnik co najwyżej losowo, wówczas funkcja nie będzie wartością logiczną. $d$ $d2^d$ $n \leq d2^d$ $d2^d$ $d2^d$ $d$ $d$

Pytanie zatem brzmi: czy istnieje sposób na wypróbowanie funkcji logicznej niskiego stopnia, która pozwala uniknąć tych dwóch problemów?

randomness boolean-functions bounded-degree Igor Shinkar
źródło

Chcesz rzeczywista funkcja będzie ograniczenie realnego wielomianem stopnia do 0-1 wejść, czy też ma to być, że wtedy i tylko wtedy dla prawdziwych wielomianu z stopień co najwyżej ? Albo coś innego?

d

$d$

f (x) = 1

$f(x) = 1$

p (x) > 0

$p(x) > 0$

p

$p$

d

$d$

Joshua Grochow

@JoshuaGrochow Chcę funkcji, której rozszerzenie Fouriera ma stopień . To twoja pierwsza opcja.

d

$d$

Igor Shinkar

Jaki jest twój model Zapisanie próbkowanej funkcji zajmuje czasu lub jeśli chcesz wyprowadzić rozszerzenie Fouriera. Czy jest stałą stałą?

2^{n}

$2^n$

n^{O (d)}

$n^{O(d)}$

d

$d$

MCH

Dodałem więcej szczegółów w pytaniu.

Igor Shinkar

@MCH Jeśli funkcja ma stopień (z zerową masą powyżej poziomu ), to nie może zależeć od więcej niż współrzędnych . Jest to wynik dzięki Nisanowi i Szegedy. Pomyśl o szczególnym przypadku . W tym przypadku wiemy, że funkcja zależy od (co najwyżej) 1 współrzędnej.

d

$d$

d

$d$

d 2^{d}

$d2^d$

d = 1

$d=1$

Igor Shinkar

Odpowiedzi:

Oto algorytm, który przewyższa trywialne próby.

Znanym faktem jest (Ćwiczenie 1.12 w książce O'Donnella): Jeśli $f:\{-1,1\}^n\to\{-1,1\}$ jest funkcją logiczną, która ma stopień $\le d$ jako wielomian, to każdy współczynnik Fouriera z $f$ , jest całkowitą wielokrotnością . Używając Cauchy'ego-Schwarza i Parsevala uzyskuje się, że istnieją maksymalnie niezerowe współczynniki Fouriera i $\hat{f}(S)$ $2^{-d}$ $4^d$ $\sum_{S}{|\hat{f}(S)|}\le 2^{d}$ .

Sugeruje to metodę próbkowania -

Wybierz losowe nieujemne liczby całkowite $a_S$ dla wszystkich zbiorów $S\subseteq[n]$ wielkości co najwyżej $d$ , które sumują się do $\le 4^d$ .
Niech $f(x) = \sum_{S}{\frac{a_S}{2^d} \chi_S(x)}$ .
Sprawdź, czy jest wartością logiczną. Jeśli tak, zwróć . W przeciwnym razie wróć do . $f$ $f$ $1$

Należy zauważyć, że dla każdego stopnia wielomian dokładnie jeden wybór losowych liczb w kroku 1 wygeneruje wielomianu . Prawdopodobieństwo uzyskania określonego wielomianu wynosi Dlatego musimy powtórzyć ten proces co najwyżej razy, w oczekiwaniu, przed zatrzymaniem. $\le d$ $f$ $f$ $\le d$

1 / (\binom{(\binom{n}{\leq d}) + 4^{d}}{4^{d}}) = 1 / O (n / d)^{d 4^{d}} .

$1/\binom{\binom{n}{\le d}+4^d}{4^d} =1/O(n/d)^{d4^d}.$

O (n / d)^{d 4^{d}}

$O(n/d)^{d4^d}$

Pozostaje pokazać, jak wykonać krok 3. Można zdefiniować . Sprawdź, czy (który powinien posiadać według Nisana-Szegedy każdej logicznej funkcji), a następnie ocenić wszystkie możliwe do przypisania w zmiennych . Można to zrobić w czasie . Gur i Tamuz oferują znacznie szybszy randomizowany algorytm do tego zadania, jednak ponieważ ta część nie dominuje złożoności czasowej, to wystarczy. $A = \bigcup\{S:a_S\neq 0\}$ $|A| \le d 2^d$ $f$ $A$ $2^{d 2^d}$

Ogólnie algorytm generuje losową próbkę stopnia wielomianu w czasie . Przy założeniu, że złożoność czasowa wynosi . $\le d$ $O(\frac{n}{d})^{d4^d}$ $n \le d2^d$ $2^{O(d^2 4^d)}$

Nie jest wielomianem czasu próbkowania algorytmu, ale jest o wiele szybsze pobieranie próbek całkowicie funkcji losowej (w tym przypadku prawdopodobieństwo uzyskania stopnia konkretnego wielomian ). $\le d$ $1/2^{2^n}$

Avishay Tal
źródło

Miły! W rzeczywistości daje to algorytm, który whp (wrt ) wyprowadza maksymalną możliwą liczbę współrzędnych, od których może zależeć funkcja niskiego stopnia. Wystarczy wziąć aby było wystarczająco duże, próbkuj wiele funkcji i dla każdej funkcji policz liczbę wpływowych współrzędnych. Wydaj maksimum, które widzisz.

d

$d$

n = 10 d 2^{d}

$n = 10d2^{d}$

Igor Shinkar