Skip to content

ICM Survey: Sum-of-squares proofs and the quest toward optimal algorithms

April 21, 2014

I have just posted online a new survey “Sum-of-Squares proofs and the quest toward optimal algorithms” co-authored with David Steurer .

The survey discusses two topics I have blogged about before – Khot’s Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method – and the connections between them. Both are related to the notion of meta algorithms. While typically we think of an algorithm as tailor-made for a particular problem, there are some generic approaches to design an “algorithmic scheme” or a meta algorithm, that can be applied to a large class of problems. The UGC predicts that a particular such meta-algorithm, which we call in the survey simply the “UGC Meta-Algorithm”, would give in fact optimal approximation guarantees among all efficient algorithms for a large class of problems. This is very exciting from the point of view of complexity theory, not simply because it gives many hardness-of-approximation results in one shot, but because in some sense it gives a complete understanding of what makes problems of certain domains easy or hard.

The SOS method is another meta algorithm that can be applied to the same cases. It is parameterized by a number \ell called its degree. Using a higher degree can give potentially better approximation guarantees, at the expense of longer running time: running the method with degree \ell on input of length n takes n^{O(\ell)} time. The UGC Meta-Algorithm in fact corresponds to the base case (which is degree \ell=2) of the SOS method, and so the UGC predicts that in a great many cases, using constant (even even mildly super-constant) degree larger than 2 will not help get better approximation guarantees. We discuss in the survey a few recent results that, although falling short of refuting the UGC, cast some doubts on this prediction by showing that larger degree can sometimes help in somewhat similar contexts. I will give a talk on the same topic in the mathematical aspects of computer science section  of the 2014 International Congress of Mathematicians to be held in Seoul, South Korea, August 13-21, 2014. As you can see, there will be some great speakers in this session (and ICM in general), and I hope we will see blog posts on some of those surveys as well.

3 Comments leave one →
  1. Suresh permalink
    January 27, 2015 9:15 pm

    Hi Boaz,
    I was watching your ICM talk, and unfortunately the camera is focused in such a way that the slides are almost unreadable. I was wondering if you had slides for the talk available so I could use that as an accompaniment to your talk and the survey (some of us are organizing an informal reading group around it)

    • January 28, 2015 9:18 pm

      Thank you Suresh for your interest! I have just posted on the webpage for my seminar series on this topic
      links to slides for several versions of this talk, as well as to videos of a 4-part lecture series by David Steurer which you may find useful.


  1. ICM survey: Computing on the edge of chaos | Windows On Theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: