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
Automata TheoryStanford University via edX Intro to Theoretical Computer Science
Udacity Computing: Art, Magic, Science
ETH Zurich via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera