Events by date

Please note: This master’s thesis presentation will take place in DC 2310 and online.

Gengyi Sun, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Shane McIntosh

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.