TY - GEN

T1 - The power of sum-of-squares for detecting hidden structures

AU - Hopkins, Samuel B.

AU - Kothari, Pravesh K.

AU - Potechin, Aaron

AU - Raghavendra, Prasad

AU - Schramm, Tselil

AU - Steurer, David

PY - 2017/11/10

Y1 - 2017/11/10

N2 - We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: The twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables.We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program.Using related ideas on SoS algorithms and lowdegree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK+16]), we prove a new SoS lower bound for the tensor PCA problem.

AB - We study planted problems-finding hidden structures in random noisy inputs-through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of powerful semidefinite programs has recently yielded many new algorithms for planted problems, often achieving the best known polynomial-time guarantees in terms of accuracy of recovered solutions and robustness to noise. One theme in recent work is the design of spectral algorithms which match the guarantees of SoS algorithms for planted problems. Classical spectral algorithms are often unable to accomplish this: The twist in these new spectral algorithms is the use of spectral structure of matrices whose entries are low-degree polynomials of the input variables.We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-ksubgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of degree d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program.Using related ideas on SoS algorithms and lowdegree matrix polynomials (and inspired by recent work on SoS and the planted clique problem [BHK+16]), we prove a new SoS lower bound for the tensor PCA problem.

KW - average-case algorithms

KW - average-case hardness

KW - semidefinite programming

KW - spectral algorithms

KW - sum of squares

UR - http://www.scopus.com/inward/record.url?scp=85041096137&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041096137&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.72

DO - 10.1109/FOCS.2017.72

M3 - Conference contribution

AN - SCOPUS:85041096137

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 720

EP - 731

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

Y2 - 15 October 2017 through 17 October 2017

ER -