Open Problems

Lecture 4: Goemans-Williamson

1. Can we find a subexponential time algorithm which beats Goemans-Williamson?

2. Can we prove a constant degree SOS lower bound on MAX-CUT for an approximation ratio lower than 16/17?

Lecture 7: Arora-Rao-Vazirani

1. Can SOS do better than the Goemans-Linial relaxation? Can we prove a constant degree SOS lower bound for some superconstant approximation ratio?

2. Can we prove a lower bound of (log n)^(1/2) for sparsest cut on unweighted graphs as well as weighted graphs?

1. With a more careful analysis, can we remove the logarithmic factors in the norm bounds?

2. More ambitiously, can we determine the spectrums of these matrices?

1. Can we prove the full lower bound on planted clique with the exact constraint that the sum of the x_i is k?

2. How close to (n)^(1/2) can we make the lower bound?

1. What can we say when d > n^(1/2) and k > n²/d² where d is the dimension of the subspace and k is the sparsity of the planted vector?

1. Under what conditions on the input tensor T does SOS solve the exact tensor completion problem given randomly sampled entries? For example, does SOS succeed on rank r tensors whose components are random vectors when r << n^(3/2)?

1. What is the performance of SOS on unique games and on small set expansion? Can we prove a lower bound for constant degree SOS?