Aaronson (STOC 2010) conjectured that almost $k$-wise independence fools constant-depth circuits; he called this the generalised Linial-Nisan conjecture. Aaronson himself later found a counterexample for depth-3 circuits. We give here an improved counterexample for depth-2 circuits (DNFs). This shows, for instance, that Bazzi's celebrated result ($k$-wise independence fools DNFs) cannot ... more >>>

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ satisfies
\[
0.847... ~\leq~ \alpha ~\leq~ 0.965...\ .
\]
Determining $\alpha$ is one of the ... more >>>