Computational Complexity
Videos from BIRS Workshop
Gil Cohen, Tel Aviv University
Monday Sep 5, 2016 09:04 - 09:52
Recent advances in randomness extractors and applications
David Zuckerman, University of Texas, Austin
Monday Sep 5, 2016 10:10 - 10:54
Explicit Two-Source Extractors and Resilient Functions
Eshan Chattopadhyay, UT Austin
Monday Sep 5, 2016 10:59 - 11:31
Alternating Extraction, and its applications to Non-Malleable Extractors
Avi Wigderson, Institute for Advanced Study
Monday Sep 5, 2016 13:12 - 14:02
Theory and applications of operator scaling (I)
Ankit Garg, Microsoft Research
Monday Sep 5, 2016 14:22 - 15:13
Theory and applications of operator scaling (II)
Benjamin Rossman, University of Toronto
Monday Sep 5, 2016 15:36 - 16:02
The Formula Complexity of Subgraph Isomorphism
Venkatesan Guruswami, UC Berkeley
Monday Sep 5, 2016 16:04 - 16:33
What fraction of worst-case bit deletions are correctable?
Boaz Barak, Harvard
Tuesday Sep 6, 2016 09:03 - 09:58
Sum of squares and computational bayesanism
David Steurer, Cornell University
Tuesday Sep 6, 2016 10:15 - 11:07
Polynomial-time tensor decomposition with sum-of-squares
Tselil Schramm, Stanford
Tuesday Sep 6, 2016 11:14 - 12:05
Strongly refuting random constraint satisfaction problems below the spectral threshold
Robert Robere, DIMACS
Tuesday Sep 6, 2016 14:04 - 15:04
Exponential Lower Bounds for Monotone Computation by Algebraic Gaps
Raghu Meka, UCLA
Tuesday Sep 6, 2016 15:33 - 16:05
Approximating CSPs requires sub-exponential size linear programs
Dana Moshkovitz, University of Texas - Austin
Tuesday Sep 6, 2016 16:07 - 16:38
Candidate Hard Unique Game
Amir Shpilka, Tel Aviv University
Wednesday Sep 7, 2016 11:08 - 12:01
Proof complexity lower bounds from algebraic circuit complexity
Ran Raz, Princeton University
Thursday Sep 8, 2016 09:02 - 09:55
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Marco Carmosino, Simon Fraser University
Thursday Sep 8, 2016 10:15 - 11:02
Learning algorithms from natural proofs
Rahul Santhanam, University of Oxford
Thursday Sep 8, 2016 11:09 - 11:53
Stronger Connections between Learning, Lower Bounds and Pseudorandomness
Daniel Kane, UCSD
Thursday Sep 8, 2016 13:15 - 14:04
A New Approach to Distribution Testing
Shachar Lovett, University of California San Diego
Thursday Sep 8, 2016 14:10 - 15:01
Structure of protocols for XOR functions
Oded Regev, New York University
Thursday Sep 8, 2016 16:08 - 17:03
The Reverse Minkowski Theorem
Scott Aaronson, UT Austin
Thursday Sep 8, 2016 20:04 - 20:58
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Shubhangi Saraf, Rutgers
Friday Sep 9, 2016 08:38 - 09:06
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Rutgers
Friday Sep 9, 2016 09:07 - 09:34
Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
