Tselil Schramm

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2017-129

July 18, 2017

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-129.pdf

We study the Sum-of-Squares semidefinite programming hierarchy via the lens of average-case problems.

The Sum-of-Squares Hierarchy is a formulaic family of convex relaxations to polynomial optimization problems, which allows one to trade runtime for accuracy in a smooth manner. The Hierarchy has been studied since the early 2000’s, both from the perspective of optimization and control and as a proof system. In the past five years, the Hierarchy has become a focus of intensive study in the theory of computation community. This is because recent results give us reason to hope that Sum-of-Squares algorithms may refute important conjectures on hardness of approximation. However, our understanding of the guarantees of the Hierarchy remains relatively incomplete.

In this dissertation, we present three results which make modest progress towards understanding the power and limitations of the Sum-of-Squares Hierarchy; all three works use average-case problems as a lens for the Sum-of-Squares algorithms, by enabling us to use random matrix theory as a tool in the analysis.

First, we analyze the performance of the Hierarchy for strongly refuting random constraint satisfaction problems (CSPs). We obtain a full characterization of the Sum-of-Squares Hierarchy for strong refutation of random CSPs, and give new subexponential-time strong refutation algorithms for CSPs with super-linear density.

Next, we give impossibility results for solving the planted clique problem via a Sum-of-Squares algorithm, demonstrating that the degree-4 Sum-of-Squares algorithm cannot distinguish graphs which contain a planted clique from uniformly random graphs.

Finally, even in the asymptotically polynomial-time regime, the Sum-of-Squares algorithm is often prohibitively slow. We show that for average-case problems, polynomial-time Sum-of-Squares algorithms can often be replaced with fast spectral algorithms, which run in linear or near-linear time in the input size.

Advisors: Satish Rao and Prasad Raghavendra

---

BibTeX citation:

@phdthesis{Schramm:EECS-2017-129,
    Author= {Schramm, Tselil},
    Title= {Random Matrices and the Sum-of-Squares Hierarchy},
    School= {EECS Department, University of California, Berkeley},
    Year= {2017},
    Month= {Jul},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-129.html},
    Number= {UCB/EECS-2017-129},
    Abstract= {We study the Sum-of-Squares semidefinite programming hierarchy via the lens of average-case problems.

The Sum-of-Squares Hierarchy is a formulaic family of convex relaxations to polynomial optimization problems, which allows one to trade runtime for accuracy in a smooth manner. The Hierarchy has been studied since the early 2000’s, both from the perspective of optimization and control and as a proof system. In the past five years, the Hierarchy has become a focus of intensive study in the theory of computation community. This is because recent results give us reason to hope that Sum-of-Squares algorithms may refute important conjectures on hardness of approximation. However, our understanding of the guarantees of the Hierarchy remains relatively incomplete.

In this dissertation, we present three results which make modest progress towards understanding the power and limitations of the Sum-of-Squares Hierarchy; all three works use average-case problems as a lens for the Sum-of-Squares algorithms, by enabling us to use random matrix theory as a tool in the analysis.

First, we analyze the performance of the Hierarchy for strongly refuting random constraint satisfaction problems (CSPs). We obtain a full characterization of the Sum-of-Squares Hierarchy for strong refutation of random CSPs, and give new subexponential-time strong refutation algorithms for CSPs with super-linear density. 

Next, we give impossibility results for solving the planted clique problem via a Sum-of-Squares algorithm, demonstrating that the degree-4 Sum-of-Squares algorithm cannot distinguish graphs which contain a planted clique from uniformly random graphs.

Finally, even in the asymptotically polynomial-time regime, the Sum-of-Squares algorithm is often prohibitively slow. We show that for average-case problems, polynomial-time Sum-of-Squares algorithms can often be replaced with fast spectral algorithms, which run in linear or near-linear time in the input size.},
}

EndNote citation:

%0 Thesis
%A Schramm, Tselil 
%T Random Matrices and the Sum-of-Squares Hierarchy
%I EECS Department, University of California, Berkeley
%D 2017
%8 July 18
%@ UCB/EECS-2017-129
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-129.html
%F Schramm:EECS-2017-129