Algorithms and Complexity Seminar

Amir Shpilka: Reed-Muller Codes for Random Erasures and Errors
Wednesday, September 30, 2015 - 4:00pm to 5:00pm
Morteza Zadimoghaddam: Randomized Composable Core-sets for Distributed Submodular and Diversity Maximization
Friday, September 11, 2015 - 4:00pm to 5:00pm
Cameron Musco: Dimensionality Reduction for k-Means 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 k-rank approximation problems. Importantly, this class of problems includes k-means 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 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.

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 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.

Pages

Subscribe to Algorithms and Complexity Seminar