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 infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified 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”.


Subscribe to Algorithms and Complexity Seminar