Spring 2013

2013/06/12: Jelani Nelson, "OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings"

Jelani Nelson (IAS/Harvard)

2013/05/22: Thomas Rothvoss, "Approximate bin packing with O(log OPT  log log OPT) bins"

Thomas Rothvoss (MIT)

2013/05/08: C. Seshadri, "Monotonicity testing, alternating paths, directed isoperimetry, and strawberries"

C. Seshadri (Sandia National Labs)

2013/04/24: Alexander Sherstov, "Making polynomials robust to noise"

Alexander Sherstov (UCLA)

2013/04/10: Greg Valiant, "Estimating the unseen: optimal estimators for entropy, support size, and other properties"

Greg Valiant (MSR New England)

2013/03/20: Nisheeth Vishnoi, "Evolution Through the Lens of Theory"

Nisheeth Vishnoi (MSR Bangalore)

2013/03/06: Raghu Meka, "Beating the Union Bound via Geometric Techniques"

Raghu Meka (IAS and DIMACS)

2013/02/20: Anup Rao, "Direct Products in Communication Complexity"

Anup Rao (University of Washington)

2013/02/06: Ronald de Wolf, "Exponential Lower Bounds for Polytopes in Combinatorial Optimization"

Ronald de Wolf (CWI Amsterdam and University of Amsterdam)