Algebraic Techniques in Computational Complexity

Videos from BIRS Workshop 19w5088

, Carnegie Mellon University
- 10:06
Explicit near-Ramanujan graphs of every degree
Watch video | Download video: 201907080910-ODonnell.mp4 (354M)
, University of Texas - Austin
- 11:00
Nearly Optimal Pseudorandomness From Hardness
Watch video | Download video: 201907081007-Moshkovitz.mp4 (342M)
, Cornell University and IAS
- 11:56
Pseudorandomness from the Fourier Spectrum
Watch video | Download video: 201907081117-Chattopadhyay.mp4 (246M)
, UT Austin
- 14:19
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
Watch video | Download video: 201907081331-Hoza.mp4 (319M)
, Rutgers University
- 10:53
Factors of sparse polynomials: structural results and some algorithms
Watch video | Download video: 201907090958-Saraf.mp4 (360M)
, Tel Aviv U
- 12:09
Sylvester-Gallai Type Theorems for Quadratic Polynomials
Watch video | Download video: 201907091117-Shpilka.mp4 (212M)
, MIT
- 14:23
Efficient Construction of Rigid Matrices Using an NP Oracle
Watch video | Download video: 201907091332-Alman.mp4 (148M)
, Simon Fraser University
- 12:11
Query-to-Communication lifting using low-discrepancy gadgets
Watch video | Download video: 201907101118-Koroth.mp4 (402M)
, Tata Institute of Fundamental Research
- 09:56
The Log-Approximate-Rank Conjecture is False
Watch video | Download video: 201907110904-Chattopadhyay.mp4 (402M)
, University of California San Diego
- 10:57
The sunflower conjecture and connections to TCS
Watch video | Download video: 201907111001-Lovett.mp4 (430M)
, Boston University
- 14:31
Private hypothesis selection
Watch video | Download video: 201907111334-Bun.mp4 (355M)
, University of Toronto
- 09:52
Criticality and decision-tree size of regular AC^0 functions
Watch video | Download video: 201907120905-Rossman.mp4 (302M)
, MSR India
- 10:48
Reconstructing arithmetic formulas using lower bound proof techniques
Watch video | Download video: 201907120952-Kayal.mp4 (373M)
, University of Colorado at Boulder
- 11:55
Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism
Watch video | Download video: 201907121102-Grochow.mp4 (359M)