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.