September 13, 2010Efficiently Learning Gaussian Mixtures
Greg Valiant
UC Berkeley
September 22, 2010EECS Colloquium: Towards Universal Semantic Communication
Madhu Sudan
Microsof Research, New England
Notice nonstandard date and location: Wednesday, September 22, in 306 Soda Hall
September 27, 2010PHAST: Hardware-Accelerated Shortest Path Trees
Daniel Delling
Microsoft Research, Silicon Valley
October 4, 2010 Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs
Aleksander Mądry
MIT
October 11, 2010All pairs shortest paths in quadratic time with high probability
Yuval Peres
Microsoft Research, Redmond
October 22, 2010Geometric Complexity Theory Approach to the P vs NP Problem
Ketan Mulmuley
University of Chicago
Notice nonstandard date and location: Friday, October 22, 1pm, in 410 Hearst Mining Building
October 25, 2010 No Seminar due to FOCS 2010
November 1, 2010 Correspondence of Computational and Statistical Physics Threhsolds.
Allan Sly
Microsoft Research, Redmond
November 8, 2010Applications of FT-Mollification
Jelani Nelson
MIT
November 22, 2010Non-Uniform ACC Circuit lLower Bounds
Ryan Williams
IBM Almaden
November 29, 2010A Strong Parallel Repetition Theorem for Projection Games on Expanders
Ricky Rosen
Weizmann Institute
December 6, 2010A regularity lemma for Polynomial Threshold Functions
Ilias Diakonikolas
UC Berkeley
January 24, 2011Probabilistic Approximation Theorems in Game Theory and Stochastic Optimization
Costis Daskalakis
MIT
January 31, 2011Subexponential Algorithms for Unique Games and Related Problems
David Steurer
Microsoft Research
February 7, 2011Spectral Algorithms for Graph Partitioning and Graph Decomposition
Nisheeth Vishnoi
Microsoft Research