[Colloquium] Reminder - Christopher Jones Candidacy Exam/Oct 6, 2021

[meganwoodward at uchicago.edu]

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

Remote Location:  https://uchicago.zoom.us/j/99429348217?pwd=RlU2K3lhck9MaWt1aHBQUnFPQ0cyZz09

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