Efficient Construction of Rigid Matrices Using an NP Oracle
Offered By: IEEE via YouTube
Course Description
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
Tags
Related Courses
Information TheoryThe Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera