[Colloquium] Christopher Jones Candidacy Exam/Oct 6, 2021
meganwoodward at uchicago.edu
meganwoodward at uchicago.edu
Fri Sep 24 11:21:00 CDT 2021
This is an announcement of Christopher Jones's Candidacy Exam.
===============================================
Candidate: Christopher Jones
Date: Wednesday, October 06, 2021
Time: 12 pm CST
Location: Crerar 298
Title: Sum-of-Squares for Unique Games
Abstract: The Sum-of-Squares algorithm is a powerful and generic algorithm for combinatorial optimization. One of the landmark applications of the algorithm is to the Unique Games problem. I will present works that show that the Sum-of-Squares algorithm solves Unique Games in polynomial time on certain classes of input graphs, and that it solves Unique Games in subexponential time on general graphs. Despite this, it is still unknown whether Sum-of-Squares solves Unique Games on all graphs in polynomial time. Sum-of-Squares is perhaps our most powerful candidate for attacking Unique Games, and understanding its power and limitations is a pressing concern.
Advisors: Aaron Potechin
Committee: Aaron Potechin, Laci Babai, and Madhur Tulsiani
More information about the Colloquium
mailing list