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. 

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. 

Matt Coudron: Infinite Randomness Expansion with a Constant Number of Devices Thursday, January 23, 2014  4:00pm to 5:00pm We present a deviceindependent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves inﬁnite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certiﬁed randomness that is exp(−Ω 

Michael Kapralov: Approximating Matching Size from Random Streams Wednesday, December 18, 2013  4:00pm to 5:00pm We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. 

Arnab Bhattacharyya: Algorithmic regularity for polynomials and applications Friday, December 13, 2013  1:30pm to 2:30pm In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a collection of polynomials F={P1,...,Pm} to a new collection F′, so that the polynomials in F′ are “pseudorandom”. 