Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Unique Games, Sum-of-Squares, and the Quest for Optimal Algorithms
Speaker:Prof. David Steurer
coming from:Cornell University, Ithaca, USA
Speakers Bio: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.

Event Type:MPI Colloquium Series Distinguished Speaker
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Language:English
Date, Time and Location
Date:Monday, 7 July 2014
Time:14:15
Duration:60 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Jennifer Müller
Phone:2900
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Jennifer Müller, 07/01/2014 03:06 PM -- Created document.