2014/2/26: Boaz Barak (Microsoft)
Fun and Games with Sums of Squares
2014/2/12: Shubhangi Saraf (Rutgers)
On Breaking the quadratic barrier for 3-LCCs over the Reals
2014/1/29: Subhash Khot (NYU)
On Approximation Resistance of Predicates
2013/12/4: David Steurer (Cornell)
Approximate Constraint Satisfaction Requires Large LP Relaxations
2013/11/20: Sanjam Garg (UCLA)
Candidate Indistinguishability Obfuscation for all circuits and its Applications
(Presentations start about 3:10 in, talk at 7:00)
2013/11/06: Lorenzo Orecchia (MIT Math)
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
2013/10/23: Nikhil Srivastava (MSR India)
Interlacing Families, Mixed Characteristic Polynomials and the Kadison-Singer Problem
Download in MP4 (802MB)
2013/10/09: Shachar Lovett (UCSD)
Communication is Bounded by Root of Rank
(Talk starts around 2:30)
Download in MP4 (404MB)
2013/09/25: Ankur Moitra (MIT)
A Polynomial Time Algorithm for Lossy Population Recovery
(Talk starts around 4:00)
Download in MP4 (627MB)
2013/09/11: Ramprasad Saptharishi (MSR India)
Arithmetic Circuits: Depth reductions, chasms and escalators
(Talk starts around 6:30)Download an mp4 of the talk directly here (356MB).
2013/06/12: Jelani Nelson (IAS/Harvard)
OSNAP: Faster numerical linear algebra algorithms via sparser
Download an mp4 of the talk directly here (233MB).
2013/05/22: Thomas Rothvoss (MIT)
Approximate bin packing with O(log OPT . log log OPT) bins.
Download an mp4 of the talk directly here (161MB).
2013/05/08: C. Seshadri (Sandia National Labs)
Monotonicity testing, alternating paths, directed isoperimetry, and strawberries
2013/04/24: Alexander Sherstov (UCLA)
Making polynomials robust to noise
(Talk starts around 4:25)
Download an mp4 of the talk directly here (219MB).
2013/04/10: Greg Valiant (MSR New England)Estimating the unseen: optimal estimators for entropy, support size, and other properties
(Talk starts around 7:00)
Download an mp4 of the talk directly here (220MB).
2013/03/20: Nisheeth Vishnoi (MSR Bangalore)
Evolution Through the Lens of Theory
(Talk starts around 3:38)
Download an mp4 of the talk directly here (259MB).
2013/03/06: Raghu Meka (IAS and DIMACS)
Beating the Union Bound via Geometric Techniques
Download an mp4 of the talk directly here (201MB).
2013/02/20: Anup Rao (University of Wahington)
Direct Products in Communication Complexity
Download an mp4 of the talk directly here (241MB).
Slides for the talk are available: PDF
See also here for the paper.
2013/02/06: Ronald de Wolf (CWI Amsterdam and University of Amsterdam)
Exponential Lower Bounds for Polytopes in Combinatorial Optimization