MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Unique Games, Sum-of-Squares, and the Quest for Optimal Algorithms

Prof. David Steurer
Cornell University, Ithaca, USA
MPI Colloquium Series Distinguished Speaker

David Steurer is an Assistant Professor in the Department
of Computer Science at Cornell University. He gradudated
from Princeton University in 2010, and obtained his Master's
and Bachelor's degrees from Saarland University in 2006.
David's work on subexponential algorithms for unique games
has won the FOCS Best Paper Award in 2010, and his dissertation
earned an honorable mention for the ACM Dissertation Award.
In 2014, David has been awarded with an Alfred P. Sloan Fellowship.
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience
English

Date, Time and Location

Monday, 7 July 2014
14:15
60 Minutes
E1 4
024
Saarbrücken

Abstract

In order to achieve strong guarantees, it’s common practice to tailor our algorithms as much as possible to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture and the Sum-of-Squares method, surprisingly suggest that this tailoring is not necessary and that instead a single concrete “meta-algorithm” could achieve best-possible guarantees for a wide range of different problems.

The Unique Games Conjecture (UGC) is a tantalizing conjecture in computational complexity, which, if true, would shed light on the complexity of a great many problems. In particular, this conjecture predicts that a single concrete algorithm provides optimal guarantees among all efficient algorithms for a large class of computational problems.
The Sum-of-Squares (SOS) method is a conceptually simple but powerful approach for solving systems of polynomial constraints. This approach is studied in several scientific disciplines, including real algebraic geometry, proof complexity, control theory, and mathematical programming, and has found applications in fields as diverse as quantum information theory, formal verification, game theory, and machine learning.
We survey recently uncovered connections between the Unique Games Conjecture and the Sum-of-Squares method. In particular, we discuss new tools to rigorously bound the running time of the SOS method for obtaining approximate solutions to hard optimization problems, and how these tools give the potential for the sum-of-squares method to provide new guarantees for many problems of interest, and possibly to even refute the UGC.

Contact

Jennifer Müller
2900
--email hidden
passcode not visible
logged in users only

Jennifer Müller, 07/01/2014 15:06 -- Created document.