MIAO/BARC talk by Artur Riazanov

Monday, 19 May 2025, Artur Riazanov, PhD student at the École Polytechnique Fédérale de Lausanne, Switzerland, will give a talk on "Generalised Linial--Nisan Conjecture is False for DNFs".

Please note that the talk will be presented at HCØ, øv. A112 from 2 to 3 pm and the technical discussion will happen from 3 to 4 pm at DIKU in meeting room 2-0-04 (ground floor, to the left of the main staircase).

Abstract:
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.
Joint work with Yaroslav Alekseev, Mika Göös, Ziyi Guan, Gilbert Maystre, Dmitry Sokolov, and Weiqiang Yuan.


portrait Artur RiazanovBio:
Artur Riazanov is a PhD student at EPFL in Switzerland, advised by Mika Göös. He did a bachelor's degree at St. Petersburg State University and master's degree at St. Petersburg Academic university advised by Dmitry Itsykson. He mainly works on concrete models in computational complexity (query/circuit/proof/
communication complexity).

Host:
Susanna Rezende