Computational Complexity

Videos from BIRS Workshop 16w5044

, CalTech
- 09:52
Recent advances in randomness extractors and applications
Watch video | Download video: 201609050904-Cohen.mp4 (144M)
, University of Texas, Austin
- 10:54
Explicit Two-Source Extractors and Resilient Functions
Watch video | Download video: 201609051010-Zuckerman.mp4 (127M)
, UT Austin
- 11:31
Alternating Extraction, and its applications to Non-Malleable Extractors
Watch video | Download video: 201609051059-Chattopadhyay.mp4 (105M)
, Institute for Advanced Study
- 14:02
Theory and applications of operator scaling (I)
Watch video | Download video: 201609051312-Wigderson.mp4 (184M)
, Microsoft Research New England
- 15:13
Theory and applications of operator scaling (II)
Watch video | Download video: 201609051422-Garg.mp4 (161M)
, University of Toronto
- 16:02
The Formula Complexity of Subgraph Isomorphism
Watch video | Download video: 201609051536-Rossman.mp4 (77M)
, Carnegie Mellon University
- 16:33
What fraction of worst-case bit deletions are correctable?
Watch video | Download video: 201609051604-Guruswami.mp4 (93M)
, Harvard
- 09:58
Sum of squares and computational bayesanism
Watch video | Download video: 201609060903-Barak.mp4 (185M)
, Cornell University
- 11:07
Polynomial-time tensor decomposition with sum-of-squares
Watch video | Download video: 201609061015-Steurer.mp4 (147M)
, Simons Institute/UC Berkeley
- 12:05
Strongly refuting random constraint satisfaction problems below the spectral threshold
Watch video | Download video: 201609061114-Schramm.mp4 (157M)
, Harvard University
- 14:00
Extension Complexity of Independent Set Polytopes
Watch video | Download video: 201609061314-Goos.mp4 (153M)
, University of Toronto
- 15:04
Exponential Lower Bounds for Monotone Computation by Algebraic Gaps
Watch video | Download video: 201609061404-Robere.mp4 (207M)
, UCLA
- 16:05
Approximating CSPs requires sub-exponential size linear programs
Watch video | Download video: 201609061533-Meka.mp4 (101M)
, MIT
- 16:38
Candidate Hard Unique Game
Watch video | Download video: 201609061607-Moshkovitz.mp4 (107M)
, Tel Aviv University
- 12:01
Proof complexity lower bounds from algebraic circuit complexity
Watch video | Download video: 201609071108-Shpilka.mp4 (194M)
, Weizmann & IAS
- 09:55
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Watch video | Download video: 201609080902-Raz.mp4 (179M)
, UCSD
- 11:02
Learning algorithms from natural proofs
Watch video | Download video: 201609081015-Carmosino.mp4 (138M)
, University of Oxford
- 11:53
Stronger Connections between Learning, Lower Bounds and Pseudorandomness
Watch video | Download video: 201609081109-Santhanam.mp4 (132M)
, UCSD
- 14:04
A New Approach to Distribution Testing
Watch video | Download video: 201609081315-Kane.mp4 (161M)
, University of California, San Diego
- 15:01
Structure of protocols for XOR functions
Watch video | Download video: 201609081410-Lovett.mp4 (220M)
, New York University
- 17:03
The Reverse Minkowski Theorem
Watch video | Download video: 201609081608-Regev.mp4 (245M)
, Massachusetts Institute of Technology
- 20:58
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Watch video | Download video: 201609082004-Aaronson.mp4 (147M)
, Rutgers
- 09:06
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Watch video | Download video: 201609090838-Saraf.mp4 (78M)
, Rutgers
- 09:34
Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
Watch video | Download video: 201609090907-Kopparty.mp4 (74M)