Współczynniki Fouriera Funkcje boolowskie opisane przez obwody o ograniczonej głębokości z bramkami AND OR i XOR

Niech $f$ będzie funkcją boolowską i pomyślmy o f jako funkcji od $\{-1,1\}^n$ do $\{ -1,1 \}$ . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te $2^n$ monomialów stanowią podstawę dla przestrzeni funkcji rzeczywistych na $\{-1,1\}^n$ . Suma kwadratów współczynników wynosi po prostu $1$ więc $f$ prowadzi do rozkładu prawdopodobieństwa na jednomianach wolnych od kwadratów. Nazwijmy ten rozkład rozkładem F.

Jeśli f nie może być opisana za pomocą ograniczonego obwodu głębokości wielomianu wielkości następnie wiedzieć twierdzeniem Linial Mansour i Nisana że rozkład F jest skupiony na jednomianów $\text{polylog } n$ wielkości do niemal wykładniczo małym ciężarze. Wywodzi się to z lematu przełączającego Hastada. (Najbardziej pożądany byłby bezpośredni dowód).

Co się stanie, gdy dodamy bramki mod 2? Jednym z przykładów do rozważenia jest funkcja $IP_{2n}$ na $2n$ zmiennych, która jest opisana jako iloczyn wewnętrzny mod 2 pierwszych n zmiennych i ostatnich n zmiennych. Tutaj rozkład F jest jednolity.

Pytanie : Czy rozkład F funkcji boolowskiej jest opisany przez ograniczoną głębokość wielomianowego rozmiaru AND, OR, MOD obwodu skoncentrowanego (aż do superpolinomalnie małego błędu) na „poziomach”? $_2$ $o(n)$

Uwagi :

Jedną z możliwych ścieżek do kontrprzykładu byłoby „sklejenie” różnych adresów IP na rozłącznych zestawach zmiennych, ale nie wiem, jak to zrobić. Być może należy osłabić pytanie i pozwolić na przypisanie niektórych wag zmiennym, ale nie widzę też jasnego sposobu na zrobienie tego. (Odwołanie się do tych dwóch kwestii jest również częścią tego, o co pytam.) $_2k$
Chciałbym spekulować, że pozytywna odpowiedź na pytanie (lub do pomyślnego zmienności) będą miały zastosowanie również wtedy, gdy pozwalasz mod bramy. (Zadanie pytania było więc motywowane niedawnym imponującym wynikiem ACC Ryana Williamsa). $_k$
Dla MAJORITY rozkład F jest duży (1 / poli) dla każdego „poziomu”.

Jak pokazuje Luca, odpowiedź na zadane przeze mnie pytanie brzmi „nie”. Pozostaje pytanie, jak zaproponować sposoby znalezienia właściwości rozkładów F funkcji boolowskich, które można opisać AND AND i bramek mod 2, które nie są udostępniane przez MAJORITY.

Próba zapisania pytania, mówiąc o funkcjach MONOTONE:

$_2$ $o(n)$

$o(n)$ $\text{polylog} (n)$

— Gil Kalai
źródło

Wydaje się to bardzo silnym przypuszczeniem, byłoby bardzo interesujące, gdyby istniały dowody, że może to być prawda. Czy stoi za tym intuicja, że dla obwodów o stałej głębokości z bramkami modowymi możesz mieć funkcje, które są bardzo niewrażliwe na hałas, takie jak wielomiany niskiego stopnia, lub całkowicie losowe, takie jak parzystość, ale ciężko jest stworzyć coś w środku, jak większość?

— Boaz Barak

Drogi Boazie (oczekiwałbym kontrprzykładu na mocne sugerowane stwierdzenie). Re: intuicja, zastąp „„ całkowicie losowy ”słowem„ jak Bernouli ”. Jak pamiętam, kiedy rozważa się pojedynczą bramę mod k, wówczas rozkład F jest podobny do pewnego rozkładu Bernouli (mianowicie waga dla | S | jest jak p ^ | S | (1-p) ^ {n- | S | } dla niektórych p, niekoniecznie p = 1/2. Wygląda więc na to, że małe obwody głębokości z bramkami mod k manipulują w swoich dystrybucjach F, takich jak rozkłady Bernouli, więc być może właściwość „większości wag na kilku poziomach” (Lub niektórych innych właściwość dystrybucji Bernouli) jest zachowana

— Gil Kalai

Gil, czy coś takiego byłoby kontrprzykładem?

$m$ $n=m+\log m$ $n$ $(x,i)$ $x$ $(x_1,\ldots ,x_m)$ $i$ $1,\ldots,m$

$f(x,i):= x_1 \oplus \cdots \oplus x_i$

$i=1,\ldots,m$ $1/m$ $x_1 \oplus \cdots \oplus x_i$ $1/m^2$

f () można zrealizować na głębokości-3: umieść wszystkie XOR w warstwie, a następnie wykonaj „zaznaczenie” w dwóch warstwach AND, OR i NOT (nie licząc NOT jako dodawania do głębi, jak zwykle).

— Luca Trevisan
źródło

tak, Luca, wygląda na to, że masz rację.

— Gil Kalai