[Proof Complexity] MIAO seminar Wed Nov 27 at 14:00 CET with Anastasia Sofronova: Lower bounds beyond DNF of parities

[Jakob Nordström]

Dear all,

With apologies for the somewhat short notice, we are happy to announce 
that on Wednesday November 27 at 14:00 CET we will have a MIAO seminar 
"Lower bounds beyond DNF of parities" given by Anastasia Sofronova from 
EPFL. You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at Lund University. Local 
participants are warmly welcome to seminar room E:1124 at Klas Anshelms 
väg 10 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.

Most of our seminars consist of two parts: first a 50-55-minute regular 
talk, and then after a break a ca-1-hour in-depth technical presentation 
with (hopefully) a lot of interaction. The intention is that the first 
part of the seminar will give all listeners a self-contained overview of 
some exciting research results, and after the break people who have the 
time and interest will get an opportunity to really get into the 
technical details. (However, for those who feel that the first part was 
enough, it is perfectly fine to just discretely drop out during the 
break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can usually be found with 
somewhat better forward notice 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

**********

/Wednesday Nov 27 at 14:00 in seminar room E:1124, Klas Anshelms väg 10, 
Lund University, and on Zoom
*Lower bounds beyond DNF of parities
*(Anastasia Sofronova, EPFL)
/
We consider a subclass of AC^0[2] circuits that simultaneously captures 
DNF-Xor and depth-3 AC^0 circuits. For this class we show a technique 
for proving lower bounds inspired by the top-down approach. We give 
lower bounds for the middle slice function, inner product function, and 
affine dispersers. Joint work with Artur Riazanov and Dmitry Sokolov.


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