Special Year Seminar

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.