Fall 2014

Algebraic Geometry Fellows' Seminar

Dec. 3, 2014 2:00 pm3:00 pm

Add to Calendar


Benjamin Rossman (National Institute of Informatics, Tokyo)


Calvin Lab 116

Boolean Formulas vs. Circuits

Understanding the relative power of Boolean formulas vs. circuits (NC^1 vs. P/poly) is a central question in circuit complexity.  In this talk I will discuss recent work that gives sharp separations between formulas vs. circuits in the bounded-depth and monotone settings.