Algorithms and Complexity Seminar

	Aviad Rubinstein: Inapproximability of Nash Equilibrium Tuesday, November 25, 2014 - 4:00pm to 5:00pm We prove that finding an epsilon-approximate Nash equilibrium is PPAD-complete 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 Read-Once Algebraic Branching Programs, in Any Order" and Ali Vakilian "Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements" Thursday, May 29, 2014 - 4:00pm to 5:00pm For Hitting Sets for Multilinear Read-Once 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 Core-sets 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 core-sets" for basic diversity and coverage maximization problems. A core-set for a point-set in a metric space is a subset of the point-set
	Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring Wednesday, April 30, 2014 - 4:00pm Given a k-SAT 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 message-passing 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 device-independent 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”.

Pages