Houve algum progresso no aperto do expoente no resultado de que a independência do polilog engana

Braverman mostrou que distribuições que são -wise independente-fool profundidadecircuitos de tamanhopor "colando" a aproximação Smolensky e a aproximação de Fourier defunções booleanas -computable. O autor e aqueles que conjeturaram essa conjetura original de que o expoente lá pode ser reduzido a $(log \frac{m}{\epsilon})^{O(d^2)}$ $\epsilon$ $d$ $AC^0$ $m$ $AC^0$ $O(d)$ , e estou curioso para saber se houve algum progresso nesse sentido, pois eu imaginaria que isso envolveria a produção de um polinômio que está próximo na distância de correlação, além de concordar com a função em um grande número de entradas, e acho que seria seja uma aproximação muito interessante de encontrar sem colar esses dois juntos. Existe alguma razão para esperar que essa aproximação deva ter o grau que não era conhecido quando Braverman escreveu seu artigo em 2010? $O(d^2)$

Outra pergunta que tenho sobre este artigo é que a conjectura original se assemelha à ligação de Boppana à sensibilidade, embora tenha sido em um artigo escrito antes dessa ligação. Isso, é claro, não é uma coincidência, pois esse limite corresponderia à concentração de Fourier que você pode derivar do limite de Boppana se o polinômio de Fourier funcionasse, mas há alguma intuição melhor do que você sabe disso "se o polinômio de Fourier funcionasse , é isso que você obteria "um?

boolean-functions fourier-analysis Samuel Schlesinger
fonte

Respostas:

Em seu artigo do CCC'17 [1], Avishay Tal aprimorou o limite para

\begin{matrix} (1) & {(\log \frac{m}{ε})}^{O (d)} . \end{matrix}

$\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}$ Você pode verificar a p.15: 4 para uma discussão. Também se refere (veja a nota de rodapé 30 aum artigo de Harsha e Srinivasan, que melhora em (1)) e responde à conjectura de Tal:

k

$k$ independente dos sentidos, para

\begin{matrix} (2) & k = {(\log m)}^{O (d)} \cdot \log \frac{1}{ε} . \end{matrix}

$k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2}$ é suficiente para

ε

$\varepsilon$ -fool tamanho-

m

$m$ depth-

d

$d$ circuitos AC0.

[1] Limites apertados no espectro de Fourier de $\mathsf{AC}_0$ , A. Tal. CCC'17.

[2] Em aproximações polinomiais de $\mathsf{AC}_0$ , P. Harsha e S. Srinivasan. RANDOM 2016,

Clemente C.
fonte

@SamuelSchlesinger De nada!

Clement C.