Sea una función booleana y pensemos en f como una función desde 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.
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).
¿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.
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"?
Observaciones :
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).
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).
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 ) ?
Podemos especular que incluso podemos reemplazar por por lo que un contraejemplo para esta versión sólida puede ser interesante.
Respuestas:
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 (m n=m+logm n 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) i 1,…,m
Luego definimosf(x,i):=x1⊕⋯⊕xi
Ahora para cada la función f () tiene una correlación de 1 / m con el carácter de Fourier x 1 ⊕ ⋯ ⊕ x 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,…,m 1/m x1⊕⋯⊕xi 1/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).
fuente