[Proof Complexity] MIAO seminar Tue Dec 19 at 14:00 CET with Anastasia Sofronova: Top-down lower bounds for depth-4 circuits

[Jakob Nordström]

Dear all,

In what is looking likely to be the last seminar for the autumn semester, on Tuesday December 19 we have the pleasure of presenting a talk by Anastasia Sofronova from EPFL titled "Top-down lower bounds for depth-4 circuits". You find the abstract at the bottom of this message.

This will be a video seminar 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 be found at http://www.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

**********

Tuesday Dec 19 at 14:00 on Zoom
Top-down lower bounds for depth-4 circuits
(Anastasia Sofronova, EPFL)

We present a top-down lower-bound method for depth-4 Boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n^{1/3}. Our proof is an application of robust sunflowers and block unpredictability. This is a joint work with Mika Göös, Artur Riazanov and Dmitry Sokolov.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se