Fall 2014

Algebraic Geometry Fellows' Seminar

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.