Seminar • Algorithms and Complexity • Top-Down Lower Bounds for Depth-Four Circuits

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.