Y a-t-il eu des progrès dans le resserrement de l'exposant, si bien que l'indépendance du polylogue trompe

Braverman a montré que les distributions qui sont $(log \frac{m}{\epsilon})^{O(d^2)}$-indépendant indépendant $\epsilon$-fond profondeur $d$ $AC^0$ circuits de taille $m$ en "collant ensemble" l'approximation de Smolensky et l'approximation de Fourier de $AC^0$fonctions booléennes calculables. L'auteur et ceux qui avaient conjecturé cette conjecture originelle que l'exposant peut être réduit à$O(d)$, et je suis curieux de savoir si des progrès ont été réalisés dans ce sens, car j'imagine que cela impliquerait de produire un polynôme qui est proche de la distance de corrélation et d'être en fait d'accord avec la fonction sur un grand nombre d'entrées, et je pense que cela être une approximation très intéressante à trouver sans coller ces deux ensemble. Y a-t-il une raison de penser qu'une telle approximation doit avoir un degré$O(d^2)$ qui n'était pas connu lorsque Braverman a écrit son article en 2010?

Une autre question que j'ai sur cet article est que la conjecture originale ressemble à la limite de Boppana sur la sensibilité, bien qu'elle se trouve dans un article écrit avant cette limite. Bien sûr, ce n'est pas une coïncidence, car cette limite correspondrait à la concentration de Fourier que vous pouvez dériver de la borne de Boppana si le polynôme de Fourier fonctionnait, mais y a-t-il une meilleure intuition que vous connaissez que cela "si le polynôme de Fourier fonctionnait , c'est ce que vous obtiendrez "un?"

Dans son article CCC'17 [1], Avishay Tal a amélioré la

$$\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}$$ Vous voudrez peut-être consulter la p.15: 4 pour une discussion. Il fait également référence à (voir la note de bas de page 30 d' un article de Harsha et Srinivasan , qui s'améliore sur (1)) et répond à la conjecture de Tal:$k$-indépendant, pour $$k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2}$$ suffit pour $\varepsilon$-taille folle-$m$ profondeur-$d$ Circuits AC0.

---

[1] Limites serrées sur le spectre de Fourier de$\mathsf{AC}_0$, A. Tal. CCC'17.

[2] Sur approximations polynomiales à$\mathsf{AC}_0$, P. Harsha et S. Srinivasan. RANDOM 2016,