[Proof Complexity] MIAO seminar Mon May 19 at 14:00 CET with Artur Riazanov: The generalised Linial–Nisan conjecture is false for DNFs

[Jakob Nordström]

Dear all,

On Monday May 19 at 14:00 CET we will have the opportunity to hear a 
presentation by Artur Riazanov from EPFL, who will give a seminar titled 
"The generalised Linial–Nisan conjecture is false for DNFs". You find 
the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at the University of 
Copenhagen. Local participants are warmly welcome to Nørre campus to a 
location that will be specified later, while other participants are 
equally warmly welcome to join virtually at 
https://lu-se.zoom.us/j/61925271827 . Please feel free to share this 
information with colleagues who you think might be interested. We are 
also hoping to record the seminar and post on the MIAO Research YouTube 
channel https://youtube.com/@MIAOresearch for people who would like to 
hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Monday May 19 at 14:00 at the University of Copenhagen and on Zoom
*The generalised Linial–Nisan conjecture is false for DNFs
*(Artur Riazanov, EPFL)
/
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.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se