<p>In his <a href="http://drops.dagstuhl.de/opus/volltexte/2017/7525/" rel="nofollow noreferrer">CCC'17 paper</a> [1], Avishay Tal improved the bound to <span class="math-container">$$
\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}
$$</span>
You may want to check p.15:4 for a discussion. It also refers to (see Footnote 30 to <a href="https://arxiv.org/abs/1604.08121" rel="nofollow noreferrer">a paper of Harsha and Srinivasan</a>, which improves on (1)) and answers Tal's conjecture: <span class="math-container">$k$</span>-wise independent, for
<span class="math-container">$$
k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2}
$$</span>
suffices to <span class="math-container">$\varepsilon$</span>-fool size-<span class="math-container">$m$</span> depth-<span class="math-container">$d$</span> AC0 circuits.</p>

<hr>

<p>[1] <em>Tight Bounds on the Fourier Spectrum of <span class="math-container">$\mathsf{AC}_0$</span></em>, A. Tal. CCC'17.</p>

<p>[2] <em>On polynomial approximations to <span class="math-container">$\mathsf{AC}_0$</span></em>, P. Harsha and S. Srinivasan. RANDOM 2016,</p>

CC BY-SA 3.0
2018-04-24T05:13:41.643Z
@SamuelSchlesinger You're welcome!
Clement C.
CC BY-SA 4.0
2018-04-24T05:11:27.580Z
2018-12-31T02:51:52.047Z
2018-12-31T02:51:52.047Z
Clement C.
<p>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?</p>

<p>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?</p>

<boolean-functions><fourier-analysis>
Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?
Samuel Schlesinger
# Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?

(Asked by: username_0 on 2018-04-24)

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?

**Tags:** boolean-functions, fourier-analysis

---

## 1 answers

### Answer by username_1 on 2018-04-24. Score: 14 | Accepted answer

In his [CCC'17 paper](http://drops.dagstuhl.de/opus/volltexte/2017/7525/) [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](https://arxiv.org/abs/1604.08121), 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,

> **Comments:**
> **username_1**: @SamuelSchlesinger You're welcome!  

---

