¿Ha habido algún progreso en apretar el exponente en el resultado que la independencia de Polylog engaña a

Braverman demostró que las distribuciones que son independiente-profundidad totalcircuitos de tamaño"pegando" la aproximación de Smolensky y la aproximación de Fourier delas funciones booleanas computablesde. El autor y aquellos que habían conjeturado esto originalmente conjeturan que el exponente allí puede reducirse a $(log \frac{m}{\epsilon})^{O(d^2)}$ $\epsilon$ $d$ $AC^0$ $m$ $AC^0$ $O(d)$ , y tengo curiosidad por saber si se ha avanzado hacia esto, ya que me imagino que implicaría producir un polinomio que esté cerca en la distancia de correlación, así como también estar de acuerdo con la función en una gran cantidad de entradas, y creo que sería ser una aproximación muy interesante para encontrar sin pegar estos dos juntos. ¿Hay alguna razón para esperar que tal aproximación debe tener un grado que no se conocía cuando Braverman escribió su artículo en 2010? $O(d^2)$

Otra pregunta sobre este artículo que tengo es que la conjetura original se parece al límite de sensibilidad de Boppana, aunque fue en un documento escrito antes de este límite. Esto, por supuesto, no es una coincidencia, ya que este límite correspondería a la concentración de Fourier que puede derivar del límite de Boppana si el polinomio de Fourier funcionó, pero ¿hay alguna intuición mejor que conozca que si el polinomio de Fourier funcionara? , esto es lo que obtendrías "uno?

boolean-functions fourier-analysis Samuel Schlesinger
fuente

Respuestas:

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

$\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}$

k

$k$

\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}$

ε

$\varepsilon$

m

$m$

d

$d$

$\mathsf{AC}_0$

Clemente C.
fuente

@SamuelSchlesinger ¡De nada!

Clemente C.