2013-2014

2014/04/23: Jian Ding, "Random Constraint Satisfaction Problems and Replica Symmetry Breaking"

Jian Ding (University of Chicago)

2014/04/09: David Woodruff, "Turnstile Streaming Algorithms Might as Well be Linear Sketches"

David Woodruff (Almaden)

2014/03/26: Ryan Williams, "Faster all-pairs shortest paths via circuit complexity"

Ryan Williams (Stanford)

2014/03/12: Yury Makarychev, "Constant Factor Approximation for Balanced Cut in the Pie Model"

Yury Makarychev (TTIC)

2014/02/26: Boaz Barak, "Fun and Games with Sums of Squares"

Boaz Barak (MSR New England)

2014/02/12: Shubhangi Saraf, "On Breaking the quadratic barrier for 3-LCCs over the Reals"

Shubhangi Saraf (Rutgers)

2014/01/29: Subhash Khot, "On Approximation Resistance of Predicates"

Subhash Khot (NYU)

2013/12/04: David Steurer, "Approximate Constraint Satisfaction Requires Large LP Relaxations"

David Steurer (Cornell)

2013/11/20: Sanjam Garg, "Candidate Indistinguishability Obfuscation for all circuits and its Applications"

Sanjam Garg (UCLA)

2013/11/06: Lorenzo Orecchia, "A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time"

Lorenzo Orecchia (MIT Math)

2013/10/23: Nikhil Srivastava, "Interlacing Families, Mixed Characteristic Polynomials and the Kadison-Singer Problem"

Nikhil Srivastava (MSR India)

2013/10/09: Shachar Lovett, "Communication is Bounded by Root of Rank"

Shachar Lovett (UCSD)

2013/09/25: Ankur Moitra, "A Polynomial Time Algorithm for Lossy Population Recovery"

Ankur Moitra (MIT)

2013/09/11: Ramprasad Saptharishi, "Arithmetic Circuits:  Depth reductions, chasms and escalators"

Ramprasad Saptharishi (MSR India)