Monday, November 27, 2023 12:00 pm
-
1:00 pm
EST (GMT -05:00)
Please note: This seminar will take place in MC 5501 and online.
Mika
Göös,
Assistant
Professor
Theory
Group,
École
polytechnique
fédérale
de
Lausanne
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 with Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov.
To join this seminar in person, please go to MC 5501. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/98180200037.