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.
Bio:
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