Morteza Zadimoghaddam: Randomized Composable Coresets for Distributed Submodular and Diversity Maximization Friday, September 11, 2015  4:00pm to 5:00pm 

Cameron Musco: Dimensionality Reduction for kMeans Clustering and Low Rank Approximation Wednesday, April 1, 2015  4:00pm to 5:00pm Abstract: We show how to approximate a data matrix with a much smaller sketch that can be used to solve a general class of constrained krank approximation problems. Importantly, this class of problems includes kmeans clustering and unconstrained low rank approximation (i.e. 

Aviad Rubinstein: Inapproximability of Nash Equilibrium Tuesday, November 25, 2014  4:00pm to 5:00pm We prove that finding an epsilonapproximate Nash equilibrium is PPADcomplete for constant epsilon and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. 

John Wright: Quantum Spectrum Testing Thursday, November 13, 2014  2:00pm to 3:00pm In recent years, the area of property testing of probability distributions has produced a wide variety of interesting results. 

Michael Forbes "Hitting Sets for Multilinear ReadOnce Algebraic Branching Programs, in Any Order" and Ali Vakilian "Improved Approximation Algorithms for Degreebounded Network Design Problems with Node Connectivity Requirements" Thursday, May 29, 2014  4:00pm to 5:00pm For Hitting Sets for Multilinear ReadOnce Algebraic Branching Programs, in Any Order: 

Michael Brautbar: The Power of Local Information in Network Algorithms Friday, May 9, 2014  1:00pm to 2:00pm 

Sepideh Mahabadi: Composable Coresets for Diversity and Coverage Maximization, and Its Application in Diverse Near Neighbor Problem Wednesday, May 7, 2014  4:00pm to 5:00pm This talk consists of two parts. In the first part, we consider efficient construction of ``composable coresets" for basic diversity and coverage maximization problems. A coreset for a pointset in a metric space is a subset of the pointset 

Hardness of (2+eps)SAT and Balanced Hypergraph Coloring Wednesday, April 30, 2014  4:00pm Given a kSAT instance with the promise that there is an assignment satisfying at least t out of k literals in each clause, can one efficiently find a satisfying assignment (setting at least one literal to true in every clause)? 

Rati Gelashvili: Leader Election and Renaming with Optimal Message Complexity Wednesday, April 23, 2014  5:00pm to 6:00pm Abstract: Asynchronous messagepassing system is a standard distributed model, where $n$ processors communicate over unreliable channels, controlled by a strong adaptive adversary. 

Kyle Fox: Optimal Cuts in Surface Imbedded Graphs Wednesday, April 2, 2014  4:30pm to 5:30pm In this talk, I will describe some recent algorithmic results related to computing optimal flows and cuts in surface embedded graphs. These results are motivated by a desire to bring our understanding of efficient planar flow and cut algorithms to more general classes of graphs. 