Events
Fall 2014
Algebraic Geometry Fellows' Seminar
Wednesday, December 3rd, 2014, 2:00 pm–3:00 pm
Parent Program:
Speaker:
Benjamin Rossman (National Institute of Informatics, Tokyo)
Location:
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.
