Overview
Explore the concept of matrix rigidity and its applications in communication complexity and circuit lower bounds in this 21-minute IEEE conference talk. Delve into Williams' algorithmic approach to circuit lower bounds and learn about bootstrapping low-rank approximations. Gain insights from speakers Josh Alman and Lijie Chen as they discuss efficient construction methods for rigid matrices using an NP oracle.
Syllabus
Intro
Matrix Rigidity
Application: Communication Complexity
Application: Depth-2 Circuit Lower Bound
Williams' Algorithmic Approach to Circuit LBS
First Attempt
Bootstrapping Low-Rank Approximations
Summary
Taught by
IEEE FOCS: Foundations of Computer Science