Computational Complexity

Videos from BIRS Workshop

, Princeton University
- 09:55
Information complexity and exact communication bounds
Watch video | Download video: 201307080904-Braverman.mp4 (151M)
, University of Washington
- 11:00
Direct Products in Communication Complexity
Watch video | Download video: 201307081004-Rao.mp4 (177M)
, UCLA
- 12:14
Communication Lower Bounds Using Directional Derivatives
Watch video | Download video: 201307081115-Sherstov.mp4 (158M)
, University of California San Diego
- 14:26
Communication is bounded by root of rank
Watch video | Download video: 201307081335-Lovett.mp4 (150M)
, Institute for Advanced Study
- 15:52
Association schemes, non-commutative polynomial tail estimates, and Lasserre lower bounds for planted clique
Watch video | Download video: 201307081450-Wigderson.mp4 (171M)
, University of Toronto
- 10:06
The Complexity of the Comparator Circuit Value Problem
Watch video | Download video: 201307090908-Cook.mp4 (166M)
, University of California Berkeley
- 12:28
Approximate constraint satisfaction requires large LP relaxations
Watch video | Download video: 201307091126-Raghavendra.mp4 (179M)
, Technion
- 15:37
Succinct Computational Integrity and Privacy Research (SCIPR)
Watch video | Download video: 201307091450-BenSasson.mp4 (171M)
, New York University
- 10:04
A Characterization of Strong Approximation Resistance
Watch video | Download video: 201307100907-Khot.mp4 (228M)
, New York University
- 11:01
Non-commutative extensions of Grothendieck’s inequality
Watch video | Download video: 201307101006-Regev.mp4 (188M)
, Rutgers
- 12:10
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
Watch video | Download video: 201307101115-Kopparty.mp4 (168M)
, Harvard University
- 10:07
Pseudorandom Generators via Mild Pseudorandom Restrictions
Watch video | Download video: 201307110907-Vadhan.mp4 (240M)
, University of Texas, Austin
- 11:00
Pseudorandomness from Shrinkage
Watch video | Download video: 201307111012-Zuckerman.mp4 (135M)
, Columbia University
- 12:09
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
Watch video | Download video: 201307111115-Servedio.mp4 (146M)
, Microsoft Corporation
- 14:29
Locally Testable Codes and Derandomized Hypercubes
Watch video | Download video: 201307111338-Gopalan.mp4 (134M)
, Harvard University
- 15:27
Limits of local algorithms
Watch video | Download video: 201307111447-Sudan.mp4 (130M)
, Technion-IIT
- 10:01
Rounding group actions: examples
Watch video | Download video: 201307120908-Yehudayoff.mp4 (202M)
, Cornell University
- 11:04
Analytical Approach to Parallel Repetition
Watch video | Download video: 201307121003-Steurer.mp4 (168M)
, MIT
- 11:58
Uniform Circuit Complexity
Watch video | Download video: 201307121114-Williams.mp4 (150M)