Todas as funções cujo peso fourier está concentrado nos pequenos conjuntos calculadas pelos circuitos AC0?

Todas as funções cujo peso fourier está concentrado nos conjuntos pequenos (ou termos com baixo grau) são computadas pelos circuitos ? $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
fonte

Essa pergunta parece interessante, embora eu não tenha parte da base na análise de fourier. Eu apreciaria referências à literatura relacionada.

Markus28

@Markus: este livro 2,0 por Ryan O'Donnell é uma excelente referência: contrib.andrew.cmu.edu/~ryanod

Alessandro Cosentino

quase o inverso de Linial, Mansour, Nissan 1993 ? resultado de Aaronsons, contra-exemplo ao Linial-Nissan generalizado parece próximo? mas há IMHO tem que haver uma maneira de generalizar o resultado 1993 de alguma forma ... talvez em grande forma ....

vzn

outra idéia semelhante em vez de AC ^ 0, mais difícil de provar, seria ilimitada em profundidade, mas circuitos limitados de porta total limitados por alguma função "pequena", digamos polinomial etc ...? Também não é tão conhecida a relação entre circuitos monótonos e coeficientes de fourier ...?

vzn

ver também a independência polylogarithmic engana AC ^ 0 circuitos por Braverman

vzn

Respostas:

No. Considere a seguinte função em : $\{0,1\}^n$ Claramente, esta função é difícil para AC⁰. Por outro lado, a função é quase constante, então quase todo o seu espectro de Fourier está no primeiro nível.

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}).$

Se você quiser um contra-equilibrada, considere

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
fonte

Você tem algum exemplo robusto em que a função não pode ser aproximada em AC0?

MCH

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

A C^{0}

$AC^0$

@Arul Um nível de Fourier consiste em todos os coeficientes de Fourier correspondentes a conjuntos de um determinado tamanho. Pensamos neles como ordenados em ordem crescente de tamanho. Quanto ao motivo pelo qual essa função é difícil para AC0, este é um exercício. Dica: a paridade é difícil para AC0.

Yuval Filmus 10/10

Existem várias maneiras de entender a pergunta de acordo com o significado preciso de "tamanho pequeno" e "concentrado".

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

2) Existe um teorema de Bourgain que, se a concentração está bem acima da função majoritária, a função é aproximadamente uma Junta e, portanto, depende das variáveis O (1).

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

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

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

Gil Kalai
fonte