slideshow 3

Logic seminar

usually takes place each Monday at 16:00 in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.

Top-down depth-4 circuit lower bounds
Dmitry Sokolov
EPFL
Monday, 5. June 2023 - 16:00 to 17:30
Large lecture room at Zitna and online at https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join online
In this talk, 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. Joint work with Mika Göös, Artur Riazanov and Anastasia Sofronova