Videos

Lower Bound Barriers in Complexity Theory and Overcoming Them With Geometry

Presenter
November 25, 2024
Abstract
Chapter 14 of the classic text "Computational Complexity" by Arora and Barak is titled "Circuit lower bounds: complexity theory's Waterloo". I will discuss the lower bound problem in the context of algebraic complexity where there are barriers discovered by Efremenko-Garg-Oliveira-Wigderson. I'll begin with a history of lower bounds in the setting of tensors and conclude with a discussion of recent developments. Mathematically this is a story of going from linear algebra, to algebraic geometry and representation theory, to deformation theory and commutative algebra. No prior knowledge of the mathematics or complexity theory will be needed.