2026-08-15T11:09:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23723 2026-04-13T10:00:51Z ddc:004 open_access

Generalised Linial-Nisan Conjecture Is False for DNFs Alekseev, Yaroslav Göös, Mika Guan, Ziyi Maystre, Gilbert Riazanov, Artur Sokolov, Dmitry Yuan, Weiqiang pseudorandomness DNFs bounded independence 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yaroslav Alekseev and Mika Göös and Ziyi Guan and Gilbert Maystre and Artur Riazanov and Dmitry Sokolov and Weiqiang Yuan 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.29 urn:nbn:de:0030-drops-237231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode