9
$\begingroup$

Braverman showed that distributions which are $(log \frac{m}{\epsilon})^{O(d^2)}$-wise independent $\epsilon$-fool depth $d$ $AC^0$ circuits of size $m$ by "gluing together" the Smolensky approximation and the Fourier approximation of $AC^0$-computable Boolean functions. The author and those who had conjectured this originally conjecture that the exponent there can be reduced to $O(d)$, and I am curious if progress has been made towards this, as I'd imagine it would involve producing a polynomial which is close in correlation distance as well as actually agreeing with the function on a large number of inputs, and I think it would be a very interesting approximation to find without gluing these two together. Is there some reason to expect that such an approximation must have degree $O(d^2)$ that wasn't known when Braverman wrote his paper in 2010?

Another question about this paper I have is that the original conjecture resembles Boppana's bound on sensitivity, though it was in a paper written prior to this bound. This, of course, isn't a coincidence, as this bound would correspond to the Fourier concentration you can derive from Boppana's bound if the Fourier polynomial worked, but is there any better intuition that you know of than that "if the Fourier polynomial worked, this is what you'd get" one?

$\endgroup$
14
$\begingroup$

In his CCC'17 paper [1], Avishay Tal improved the bound to $$ \left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1} $$ You may want to check p.15:4 for a discussion. It also refers to (see Footnote 30 to a paper of Harsha and Srinivasan, which improves on (1)) and answers Tal's conjecture: $k$-wise independent, for $$ k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2} $$ suffices to $\varepsilon$-fool size-$m$ depth-$d$ AC0 circuits.


[1] Tight Bounds on the Fourier Spectrum of $\mathsf{AC}_0$, A. Tal. CCC'17.

[2] On polynomial approximations to $\mathsf{AC}_0$, P. Harsha and S. Srinivasan. RANDOM 2016,

$\endgroup$
  • $\begingroup$ @SamuelSchlesinger You're welcome! $\endgroup$ – Clement C. Apr 24 '18 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.