![Algorithms and Complexity in Algebraic Geometry_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithms%20and%20Complexity%20in%20Algebraic%20Geometry_hi-res.jpg?h=450de763&itok=r3pqykMn)
Description
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.
All scheduled dates:
Upcoming
No Upcoming activities yet