Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 10, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Alexandra Kolla (University of Illinois at Urbana-Champaign)
In this talk, I will discuss recent algorithms for the Unique Games Conjecture and explain why one of the strongest algorithms we know fails when the constrain graph is the boolean hypercube. Seen as the hypercube is a basic "bottleneck" to our understanding of how to design good algorithms for Unique Games, it is important to be able to solve UG on it. I will present a few different approaches on resolving UGC on the cube and show an integrality gap which explains why we cannot hope that the simple SDP algorithm of Goemans Williamson (which solves MaxCut exactly on the cube) fails. I will then discuss how we expect stronger SDPs to perform on the cube and conjecture that a certain SDP based algorithm approximates UGC on the hypercube very well.
This talk is based on joint past and ongoing work with Luca Trevisan, Guy Kindler, Naman Agarwal, Leonard Schulman and Aram Harrow.
Automatic MiSe System Software Version 1.4803M | admin login