Fall 2017

The Power of Hierarchies for Detecting Hidden Structures

Monday, Sep. 11, 2017 9:30 am10:30 am

Add to Calendar

We prove that for a wide class of planted problems, including refuting random constraint satisfaction problems, tensor and sparse PCA, densest-k-subgraph, community detection in stochastic block models, planted clique, and others, eigenvalues of degree-d matrix polynomials are as powerful as SoS semidefinite programs of size roughly n^d. For such problems it is therefore always possible to match the guarantees of SoS without solving a large semidefinite program.