Czy wszystkie funkcje, których waga Fouriera jest skoncentrowana na małych zestawach obliczanych przez obwody AC0?

Czy wszystkie funkcje, których waga Fouriera jest skoncentrowana na małych zestawach (lub terminach o niskim stopniu), są obliczane przez obwody ? $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
źródło

To pytanie brzmi interesująco, chociaż brakuje mi trochę tła w analizie Fouriera. Byłbym wdzięczny za odniesienia do literatury pokrewnej.

Markus

@ Markus: ta książka 2.0 autorstwa Ryana O'Donnella stanowi doskonałe źródło informacji: contrib.andrew.cmu.edu/~ryanod

Alessandro Cosentino

prawie odwrotnie do Linial, Mansour, Nissan 1993 ? wynik Aaronsona, kontrprzykład na uogólniony Linial-Nissan wydaje się bliski? ale imho muszą być sposobem na uogólnienie wyniku z 1993 roku ... może w wielkim stylu ...

dniu

innym podobnym pomysłem zamiast AC ^ 0, trudniejszym do obalenia, byłoby nieograniczenie głębokości, ale całkowite obwody ograniczone bramą ograniczone przez jakąś „małą” funkcję, powiedzmy wielomian itp.? także afaik związek między obwodami monotonicznymi i współczynnikami Fouriera nie jest tak dobrze znany ...?

vzn

patrz także polilogarytmiczni głupcy niezależni obwody AC ^ 0 autorstwa braverman

dniu

Odpowiedzi:

Nie. Rozważ następującą funkcję na : $\{0,1\}^n$ Oczywiście ta funkcja jest trudna dla AC⁰. Z drugiej strony funkcja jest prawie stała, więc prawie całe jej widmo Fouriera znajduje się na pierwszym poziomie.

f (x) = x_{0} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1}) .

$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$

Jeśli chcesz uzyskać zrównoważony kontrprzykład, rozważ Ta funkcja prawie zawsze jest równa, więc prawie całe jej widmo Fouriera znajduje się na pierwszych dwóch poziomach.

g (x) = x_{0} \oplus [x_{1} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1})] .

$g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1})\right].$

x_{0}

$x_0$

Yuval Filmus
źródło

Czy masz jakieś solidne przykłady, w których funkcji nie można aproksymować w AC0?

MCH

Funkcja skoncentrowana na pierwszych poziomach

jest zawsze zbliżona do funkcji zależnej od danych wejściowych

, więc jeśli interesują nas tylko poziomy

, to nie ma solidnych przykładów.

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

Yuval Filmus

@YuvalFilmus Co oznacza poziom widma Fouriera? Dlaczego ta funkcja jest trudna dla

A C^{0}

$AC^0$

@Arul Poziom Fouriera składa się ze wszystkich współczynników Fouriera odpowiadających zestawom o danym rozmiarze. Uważamy je za uporządkowane w porządku rosnącym według wielkości. Jeśli chodzi o to, dlaczego ta funkcja jest trudna dla AC0, jest to ćwiczenie. Wskazówka: parzystość jest trudna dla AC0.

Yuval Filmus,

Istnieje kilka sposobów, aby zrozumieć pytanie zgodnie z dokładnym znaczeniem „małego rozmiaru” i „koncentracji”.

$1-o(1)$ $S$ $1-o(1)$ ${\rm AC^0}$

2) Istnieje twierdzenie Bourgaina, że jeśli stężenie jest znacznie wyższe niż stężenie funkcji większości, wówczas funkcja jest w przybliżeniu Junta, a zatem zależy od zmiennych O (1).

$\hat f^2(S)$ $AC^0$ ${\rm polylog} (n)$

$O(\log n)$ $AC^0$

$O(polylog (n))$ $n^{polylog (n)}$

Gil Kalai
źródło