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 2 obwodu skoncentrowanego (aż do superpolinomalnie małego błędu) na o ( n ) „poziomach”?$_2$$o(n)$

Uwagi :

1. Jedną z możliwych ścieżek do kontrprzykładu byłoby „sklejenie” różnych adresów IP 2 k 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$

2. 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 k bramy. (Zadanie pytania było więc motywowane niedawnym imponującym wynikiem ACC Ryana Williamsa). $_k$

3. 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, 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).