Coeficientes de Fourier Funções Booleanas descritas por Circuitos de Profundidade Limitada com portas AND OR e XOR

Seja uma função booleana e pensemos em f como uma função de a . Nesta linguagem, a expansão de Fourier de f é simplesmente a expansão de f em termos de monômios quadrados livres. (Esses monômios formam uma base para o espaço de funções reais em . A soma dos quadrados dos coeficientes é simplesmente então leva a uma distribuição de probabilidade em monômios livres quadrados. Vamos chamar essa distribuição de distribuição F.$f$$\{-1,1\}^n$$\{ -1,1 \}$$2^n$$\{-1,1\}^n$$1$$f$

Se f pode ser descrito por um circuito de profundidade delimitada de tamanho polinomial, sabemos por um teorema de Linial, Mansour e Nisan que a distribuição F está concentrada em monômios de tamanho tamanho até peso quase exponencialmente pequeno. Isso é derivado do lema Hastad de comutação. (Uma prova direta seria mais desejável.)$\text{polylog } n$

O que acontece quando adicionamos portas mod 2? Um exemplo a considerar é a função nas variáveis , que é descrita como o produto interno mod 2 das primeiras n variáveis ​​e das últimas n variáveis. Aqui a distribuição F é uniforme.$IP_{2n}$$2n$

Pergunta : A distribuição F de uma função booleana descrita pelo tamanho polinomial de profundidade limitada AND, OR, MOD concentrada (até um erro superpolinomialmente pequeno) em "níveis"?$_2$$o(n)$

Observações :

1. Um caminho possível para um contra-exemplo seria "colar de alguma forma" vários IP em conjuntos disjuntos de variáveis, mas não vejo como fazê-lo. Talvez deva enfraquecer a questão e permitir atribuir alguns pesos às variáveis, mas também não vejo uma maneira clara de fazê-lo. (Portanto, referir-me a esses dois assuntos também faz parte do que estou perguntando.)$_2k$

2. Eu especularia que uma resposta positiva à pergunta (ou a uma variação bem-sucedida) se aplicará também quando você permitir portões mod . (Então, a pergunta foi motivada pelo impressionante resultado recente do ACC de Ryan Williams.) $_k$

3. Para MAJORITY, a distribuição F é grande (1 / poli) para cada "nível".

Como mostra Luca, a resposta para a pergunta que fiz é "não". A questão que resta é propor maneiras de encontrar propriedades das distribuições F das funções booleanas que podem ser descritas por AND OR e portas mod 2 não compartilhadas por MAJORITY.

Uma tentativa de salvar a pergunta falando sobre as funções do MONOTONE:

Pergunta : A distribuição F de uma função booleana MONOTONE descrita pelo tamanho polinomial de profundidade limitada AND, OR, MOD concentrada (até um erro superpolinomialmente pequeno) em "níveis"?$_2$$o(n)$

Podemos especular que podemos até substituir por modo que um contra-exemplo para esta versão forte possa ser interessante. $o(n)$$\text{polylog} (n)$

Gil, algo assim seria um contra-exemplo?

Seja tal que , e pense em uma entrada de bits como sendo um par que é uma sequência de bits de m e é um número inteiro no intervalo escrito em binário.m n = m + log m n ( x , i ) x ( x 1 , ... , x m ) i 1 , ... , $m$$n=m+\log m$$n$$(x,i)$$x$$(x_1,\ldots ,x_m)$$i$$1,\ldots,m$

Então definimos$f(x,i):= x_1 \oplus \cdots \oplus x_i$

Agora, para cada a função f () tem correlação com o caractere de Fourier e, portanto, o "nível i" tem pelo menos fração da massa. (De fato, mais, mas isso deve ser suficiente)i = 1 , ... , m 1 / m x 1 ⊕ ⋯ ⊕ x i 1 / m $i=1,\ldots,m$$1/m$$x_1 \oplus \cdots \oplus x_i$$1/m^2$

f () pode ser realizado na profundidade 3: coloque todos os XORs em uma camada e faça a "seleção" em duas camadas de ANDs, ORs e NOTs (sem contar os NOTs como acrescentando profundidade, como de costume).