¿Todas las funciones cuyo peso de Fourier se concentra en los conjuntos de pequeño tamaño se calculan mediante circuitos AC0?

¿Todas las funciones cuyo peso de Fourier se concentra en los conjuntos de tamaño pequeño (o términos con bajo grado) se calculan mediante circuitos ? $\mathsf{AC}^0$

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

Esta pregunta suena interesante, aunque me falta algo de antecedentes en el análisis de Fourier. Agradecería referencias a literatura relacionada.

Markus

@Markus: este libro 2.0 de Ryan O'Donnell es una excelente referencia: contrib.andrew.cmu.edu/~ryanod

Alessandro Cosentino

casi lo contrario a Linial, Mansour, Nissan 1993 ? resultado de Aaronson, ¿el contraejemplo de Linial-Nissan generalizado parece cercano? pero tengo que ser una forma de generalizar el resultado de 1993 de alguna manera ... tal vez a lo grande ...

vzn

otra idea similar en lugar de AC ^ 0, más difícil de refutar, sería la profundidad ilimitada pero los circuitos limitados de la puerta total delimitados por alguna función "pequeña", por ejemplo polinomio, etc. También afaik la relación entre circuitos monótonos y coeficientes de Fourier no es tan conocida ...?

vzn

ver también independencia pollogarítmica engaña a los circuitos AC ^ 0 por braverman

vzn

Respuestas:

No. Considere la siguiente función en : $\{0,1\}^n$ Claramente esta función es difícil para AC⁰. Por otro lado, la función es casi constante, por lo que casi todo su espectro de Fourier está en el primer nivel.

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

Si desea un contraejemplo equilibrado, considere Esta función es casi siempre igual a, por lo que casi todo su espectro de Fourier está en los dos primeros niveles.

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
fuente

¿Tiene algún ejemplo sólido en el que la función no se pueda aproximar en AC0?

MCH

Una función concentrada en los primeros niveles de

siempre está cerca de una función que depende de las entradas de

, por lo que si solo estamos interesados en los niveles de

, entonces no hay ejemplos sólidos.

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

Yuval Filmus

@YuvalFilmus ¿Qué significa el nivel del espectro de Fourier? ¿Por qué esta función es difícil para

A C^{0}

$AC^0$

@Arul Un nivel de Fourier consta de todos los coeficientes de Fourier correspondientes a conjuntos de un tamaño determinado. Pensamos en ellos como ordenados en orden creciente de tamaño. En cuanto a por qué esta función es difícil para AC0, este es un ejercicio. Sugerencia: la paridad es difícil para AC0.

Yuval Filmus

Hay varias formas de entender la pregunta de acuerdo con el significado preciso de "tamaño pequeño" y "concentrado".

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

2) Existe un teorema de Bourgain de que si la concentración está muy por encima de la de la función mayoritaria, entonces la función es aproximadamente una Junta y, por lo tanto, depende de las variables O (1).

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

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

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

Gil Kalai
fuente