Coeficientes de Fourier Funciones booleanas descritas por circuitos de profundidad acotada con compuertas AND OR y XOR

29

Sea f una función booleana y pensemos en f como una función desde {1,1}n hasta . En este lenguaje, la expansión de Fourier de f es simplemente la expansión de f en términos de monomios libres cuadrados. (Estos monomios forman una base para el espacio de funciones reales en . La suma de los cuadrados de los coeficientes es simplemente por lo que conduce a una distribución de probabilidad en monomios libres de cuadrados. Llamemos a esta distribución la distribución F.{1,1}2n{1,1}n1f

Si f puede ser descrito por un circuito de profundidad acotada de tamaño polinómico, entonces sabemos por un teorema de Linial, Mansour y Nisan que la distribución F se concentra en monomios de tamaño hasta un peso casi exponencialmente pequeño. Esto se deriva del lema de cambio Hastad. (Una prueba directa sería lo más deseable).polylog n

¿Qué sucede cuando agregamos puertas mod 2? Un ejemplo a considerar es la función en variables que se describe como el producto interno mod 2 de las primeras n variables y las últimas n variables. Aquí la distribución F es uniforme.IP2n2n

Pregunta : ¿La distribución F de una función booleana se describe por el tamaño polinómico de profundidad limitada Y, O, circuito MOD concentrado (hasta un error superpolinomialmente pequeño) en "niveles"?2o(n)

Observaciones :

  1. Una posible ruta a un contraejemplo sería "pegar de alguna manera" varias IP en conjuntos disjuntos de variables, pero no veo cómo hacerlo. Quizás uno debería debilitar la pregunta y permitir asignar algunos pesos a las variables, pero tampoco veo una forma clara de hacerlo. (Entonces, referirme a estos dos asuntos también es parte de lo que estoy preguntando).2k

  2. Yo especularía que una respuesta positiva a la pregunta, (o una variación exitosa) se aplicará también cuando permita puertas . (Entonces, formular la pregunta fue motivado por el reciente e impresionante resultado ACC de Ryan Williams). k

  3. Para MAYORIDAD, la distribución F es grande (1 / poli) para cada "nivel".

Como lo muestra Luca, la respuesta a la pregunta que hice es "no". La pregunta que queda es proponer formas de encontrar propiedades de las distribuciones F de funciones booleanas que puedan ser descritas por AND OR y compuertas mod 2 no compartidas por MAJORITY.

Un intento de guardar la pregunta hablando de las funciones MONOTONE:

Pregunta : ¿La distribución F de una función booleana MONOTONE se describe por el tamaño polinómico de profundidad limitada Y, O, el circuito MOD 2 concentrado (hasta un error superpolinomialmente pequeño) en "niveles" o ( n ) ?2o(n)

Podemos especular que incluso podemos reemplazar o(n) por polylog(n) por lo que un contraejemplo para esta versión sólida puede ser interesante.

Gil Kalai
fuente
Parece una conjetura muy fuerte, sería muy interesante si hay evidencia de que podría ser cierto. ¿Es la intuición detrás de esto que para los circuitos de profundidad constante con compuertas modulares puede tener funciones que son muy insensibles al ruido como polinomios de bajo grado, o perfectamente al azar como la paridad, pero es difícil crear algo en el medio como la mayoría?
Boaz Barak el
Estimado Booz, (esperaría un contraejemplo a la fuerte afirmación sugerida). Re: intuición, reemplace "perfectamente al azar" por "similar a Bernouli". Como recuerdo, cuando consideras una única puerta de mod k, entonces la Distribución F es como una cierta distribución de Bernouli (es decir, el peso de | S | es como p ^ | S | (1-p) ^ {n- | S | } para algunos p, no necesariamente p = 1 / 2. Por lo tanto, parece que los pequeños circuitos de profundidad acotada con compuertas mod k manipulan en sus distribuciones F, tales como las distribuciones de Bernouli, por lo que tal vez la propiedad de "la mayoría de los pesos en pocos niveles" (u otro propiedad de las distribuciones de Bernouli) se mantiene.
Gil Kalai

Respuestas:

31

Gil, ¿sería algo así como un contraejemplo?

Sea tal que n = m + log m , y piense en una entrada de n bits como un par (mn=m+logmn donde x es una cadena de m bits ( x 1 , ... , x m ) e i es un entero en el rango 1 , ... , m escrito en binario.(x,i)x(x1,,xm)i1,,m

Luego definimos f(x,i):=x1xi

Ahora para cada la función f () tiene una correlación de 1 / m con el carácter de Fourier x 1x i , por lo que el "nivel i" tiene al menos unafracción de 1 / m 2 del masa. (De hecho más, pero esto debería ser suficiente)i=1,,m1/mx1xi1/m2

f () se puede realizar en profundidad-3: coloque todos los XOR en una capa y luego haga la "selección" en dos capas de AND, OR y NOT (sin contar los NOT como agregados a la profundidad, como de costumbre).

Luca Trevisan
fuente
Sí, Luca, parece que tienes razón.
Gil Kalai