Computational Complexity
Videos from BIRS Workshop
Mark Braverman, Princeton University
Monday Jul 8, 2013 09:04 - 09:55
Information complexity and exact communication bounds
Anup Rao, University of Washington
Monday Jul 8, 2013 10:04 - 11:00
Direct Products in Communication Complexity
Alexander Sherstov, UCLA
Monday Jul 8, 2013 11:15 - 12:14
Communication Lower Bounds Using Directional Derivatives
Shachar Lovett, University of California San Diego
Monday Jul 8, 2013 13:35 - 14:26
Communication is bounded by root of rank
Avi Wigderson, Institute for Advanced Study
Monday Jul 8, 2013 14:50 - 15:52
Association schemes, non-commutative polynomial tail estimates, and Lasserre lower bounds for planted clique
Stephen Cook, University of Toronto
Tuesday Jul 9, 2013 09:08 - 10:06
The Complexity of the Comparator Circuit Value Problem
Prasad Raghavendra, University of California Berkeley
Tuesday Jul 9, 2013 11:26 - 12:28
Approximate constraint satisfaction requires large LP relaxations
Eli Ben-Sasson, Technion
Tuesday Jul 9, 2013 14:50 - 15:37
Succinct Computational Integrity and Privacy Research (SCIPR)
Subhash Khot, New York University
Wednesday Jul 10, 2013 09:07 - 10:04
A Characterization of Strong Approximation Resistance
Oded Regev, New York University
Wednesday Jul 10, 2013 10:06 - 11:01
Non-commutative extensions of Grothendieck’s inequality
Swastik Kopparty, Rutgers
Wednesday Jul 10, 2013 11:15 - 12:10
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Salil Vadhan, Harvard University
Thursday Jul 11, 2013 09:07 - 10:07
Pseudorandom Generators via Mild Pseudorandom Restrictions
David Zuckerman, University of Texas, Austin
Thursday Jul 11, 2013 10:12 - 11:00
Pseudorandomness from Shrinkage
Rocco Servedio, Columbia University
Thursday Jul 11, 2013 11:15 - 12:09
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
Parikshit Gopalan, Microsoft Corporation
Thursday Jul 11, 2013 13:38 - 14:29
Locally Testable Codes and Derandomized Hypercubes
Madhu Sudan, Harvard University
Thursday Jul 11, 2013 14:47 - 15:27
Limits of local algorithms
Amir Yehudayoff, Technion-IIT
Friday Jul 12, 2013 09:08 - 10:01
Rounding group actions: examples
David Steurer, Cornell University
Friday Jul 12, 2013 10:03 - 11:04
Analytical Approach to Parallel Repetition
Ryan Williams, MIT
Friday Jul 12, 2013 11:14 - 11:58
Uniform Circuit Complexity
