A Counterexample to the Generalized Linial-Nisan Conjecture
Alekseev, Yaroslav, Göös, Mika, Guan, Ziyi, Maystre, Gilbert, Riazanov, Artur, Sokolov, Dmitry, Yuan, Weiqiang · arXiv (Cornell University) · 2011
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 be generalised in a natural way. We also propose a way to circumvent our counterexample: We define a new notion of pseudorandomness called local couplings and show that it fools DNFs and even decision lists.