Unlocking Complexity Limits: How Geometry Breaks Barriers – Joseph Landsberg's Seminar

Special Year Seminar 10:00am|Wolfensohn Hall Topic: Lower Bound Barriers in Complexity Theory and Overcoming Them With Geometry Speaker: Joseph Landsberg Affiliation: Texas A&M University Date: November 25, 2024 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.