Overview:
The sum of squares hierarchy (SoS) is a model of
computation which has the following nice properties:
- SoS is broadly applicable.
- SoS is surprisingly powerful.
- In some sense, SoS is simple as all it uses are polynomial
equalities and the fact that squares are non-negative over the
real numbers.
For more information about SoS, see the following links:
- My course
on SoS.
- Boaz Barak and David Steurer's survey on SoS.
- Tselil Schramm's course
on SoS.
- Thomas Rothvoss's survey
on the Lasserre hierarchy (which is another name for SoS).
- Boaz Barak, Pravesh Kothari, and David Steurer's course on SoS.
- Massimo Lauria's course on
SoS.
- Toniann Pitassi's course
on proof complexity, mathematical programming, and algorithms
(which is largely about SoS).
Graph matrices are a type of matrix which arises naturally when
studying SoS and other methods which use higher moments on average
case problems. Currently, except for rough norm bounds, not much
is known about graph matrices.
Papers:
- Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis.
Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, and Aaron Potechin. FOCS 2024.
- Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs.
Pravesh Kothari, Aaron Potechin, and
Jeff Xu. STOC 2024. arXiv
- Sum-of-squares lower bounds for densest k-subgraph.
Chris Jones, Aaron Potechin, Goutham Rajendran, and
Jeff Xu. STOC 2023. arXiv
- On Mixing Distributions Via Random Orthogonal
Matrices and the Spectrum of the Singular Values of
Multi-Z Shaped Graph Matrices. Wenjun Cai and Aaron
Potechin. arXiv
- Sum-of-Squares Lower Bounds for Sparse Independent
Set. Chris Jones, Aaron Potechin, Goutham Rajendran,
Madhur Tulsiani, and Jeff Xu. FOCS 2021. arXiv
- SoS certification for symmetric quadratic functions
and its connection to constrained Boolean hypercube
optimization. Adam Kurpisz, Aaron Potechin, and
Elias Samuel Wirth. ICALP 2021. arXiv
- Exact nuclear norm, completion and decomposition for
random overcomplete tensors via degree-4 SOS. Bohdan
Kivva and Aaron Potechin. arXiv
- Machinery for Proving Sum-of-Squares Lower Bounds on
Certification Problems. Aaron Potechin and Goutham
Rajendran. arXiv
Note: A version of this paper, "Sub-exponential time
Sum-of-Squares lower bounds for Principal Components
Analysis", appeared in NeurIPS 2022.
- Sum-of-Squares Lower Bounds for
Sherrington-Kirkpatrick via Planted Affine Planes.
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones,
Aaron Potechin, Goutham Rajendran. FOCS 2020. arXiv
- The Spectrum of the Singular Values of Z-Shaped
Graph Matrices. Wenjun Cai and Aaron Potechin. arXiv
- Graph Matrices: Norm Bounds and Applications.
Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. arXiv
Note: This is a major update of the paper "Bounds on the
Norms of Uniform Low Degree Graph Matrices." which appeared
in RANDOM 2016. This paper now handles graph matrices with
hyperedges and different types of vertices. We also handle
general input distributions and show how graph matrices can
be used to simplify the proofs of several technical lemmas
in other papers.
- Sum of squares bounds for the ordering principle.
Aaron Potechin. CCC 2020. arXiv
- Sum of squares lower bounds from symmetry and a good
story. Aaron Potechin. ITCS 2019. arXiv
- A Note on Property Testing Sum of Squares and
Multivariate Polynomial Interpolation. Aaron Potechin
and Liu Yang. arXiv
- The power of sum-of-squares for detecting hidden
structures. Sam Hopkins, Pravesh Kothari, Aaron
Potechin, Prasad Raghavendra, Tselil Schramm, and David
Steurer. FOCS 2017. arXiv
- Exact tensor completion with sum-of-squares.
Aaron Potechin and David Steurer. COLT 2017. arXiv
- A Nearly Tight Sum-of-Squares Lower Bound for the
Planted Clique Problem. Boaz Barak, Sam Hopkins,
Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron
Potechin. FOCS 2016. arXiv
- On the Integrality Gap of Degree-4 Sum of Squares
for Planted Clique. Sam Hopkins, Pravesh Kothari,
Aaron Potechin, Prasad Raghavendra, and Tselil Schramm. SODA
2016. This paper merges https://arxiv.org/abs/1507.05230
and https://arxiv.org/abs/1507.05136.
- Sum-of-squares lower bounds for planted clique.
Raghu Meka, Aaron Potechin, and Avi Wigderson. STOC 2015. arXiv