Past talks

2015/02/18: Madhu Sudan (MSR)

 Imperfectly Shared Randomness in Communication. 
Slides (PPT) [Preview]

2015/02/18: Allan Sly (Berkeley)

 Proof of the satisfiability conjecture for large k. 

Allan Sly talk

Slides (PDF)


2015/02/04: Harry Buhman (CWI Amsterdam)

 Catalytic Space



2015/01/21: Zeev Dvir (Princeton University)

2-Server PIR with sub-polynomial communication

2014/12/03: Omri Weinstein (Princeton University)

Approximating the Best Nash Equilibrium in n^{o(log n)}-time Breaks the Exponential Time Hypothesis

2014/11/19: Bernhard Haeupler (Carnegie Mellon University)

Coding for Interactive Communication Made Communication Efficient and Easy

Slides (PDF)

2014/11/05: Thomas Rothvoss (University of Washington)

Constructive Discrepancy Minimization for Convex Sets

Slides (PDF)

2014/10/22: Christos Papadimitriou (UC Berkeley)

Satisfiability and Evolution

2014/10/08: Mary Wootters (Carnegie Mellon)

List-decodability of structured random codes

Slides (PDF)

2014/09/24: Ran Raz (Weizmann Institute and IAS)

Exponential separation of information and communication

2014/04/23: Jian Ding (University of Chicago)

Random Constraint Satisfaction Problems and Replica Symmetry Breaking

Slides (PDF)

2014/04/09: David Woodruff (Almaden)

Turnstile Streaming Algorithms Might as Well be Linear Sketches

2014/03/26: Ryan Williams (Stanford)

Faster all-pairs shortest paths via circuit complexity

2014/03/12: Yury Makarychev (TTIC)

Constant Factor Approximation for Balanced Cut in the Pie Model

2014/02/26: Boaz Barak (Microsoft)

Fun and Games with Sums of Squares

2014/02/12: Shubhangi Saraf (Rutgers)

On Breaking the quadratic barrier for 3-LCCs over the Reals

2014/01/29: Subhash Khot (NYU)

On Approximation Resistance of Predicates

2013/12/04: 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

2013/11/06: Lorenzo Orecchia (MIT Math)

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time

Slides (PDF)

2013/10/23: Nikhil Srivastava (MSR India)

Interlacing Families, Mixed Characteristic Polynomials and the Kadison-Singer Problem

Video (MP4) (802MB)

2013/10/09: Shachar Lovett (UCSD)

Communication is Bounded by Root of Rank

Video (MP4) (404MB)

2013/09/25: Ankur Moitra (MIT)

 A Polynomial Time Algorithm for Lossy Population Recovery

Video (MP4) (627MB)

2013/09/11: Ramprasad Saptharishi (MSR India)

Arithmetic Circuits: Depth reductions, chasms and escalators
Video (MP4) (356MB)

2013/06/12: Jelani Nelson (IAS/Harvard)

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
 

Video (MP4) (233MB)

2013/05/22: Thomas Rothvoss (MIT)

Approximate bin packing with O(log OPT  log log OPT) bins 

2013/05/08: C. Seshadri (Sandia National Labs)

Monotonicity testing, alternating paths, directed isoperimetry, and strawberries

Video (MP4) (282MB)

2013/04/24: Alexander Sherstov (UCLA)

Making polynomials robust to noise

Video (MP4) (219MB)

2013/04/10: Greg Valiant (MSR New England)

Estimating the unseen: optimal estimators for entropy, support size, and other properties

Slides (PPTX) [Preview]
Video (MP4) (220MB)

2013/03/20: Nisheeth Vishnoi (MSR Bangalore)

Evolution Through the Lens of Theory

Video (MP4) (259MB)

2013/03/06: Raghu Meka (IAS and DIMACS)

Beating the Union Bound via Geometric Techniques

Video (MP4) (201MB)

2013/02/20: Anup Rao (University of Wahington)

Direct Products in Communication Complexity

Slides (PDF)
Video (MP4) (241MB)

2013/02/06: Ronald de Wolf (CWI Amsterdam and University of Amsterdam)

Exponential Lower Bounds for Polytopes in Combinatorial Optimization