HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

DOI10.1142/9789813272880_0186zbMath1451.90113arXiv1807.11419OpenAlexW2972821478MaRDI QIDQ5122161

Prasad Raghavendra, David Steurer, Tselil Schramm

Publication date: 22 September 2020

Published in: Proceedings of the International Congress of Mathematicians (ICM 2018) (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.11419

zbMATH Keywords

polynomial systemestimation problemssum-of-squares proofs

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Related Items

Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Disordered systems insights on computational hardness ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Algorithmic obstructions in the random number partitioning problem ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Sherali-adams strikes back ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio