# SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation

arXiv: https://arxiv.org/abs/2101.01509 · HTML: https://mlsanity.com/paper/2101.01509/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 15 of 15)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)

## Built on by (most cited first, 7 of 7)

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [Robust Mean Estimation Without Moments for Symmetric Distributions](https://mlsanity.com/paper/2302.10844/) (2023)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)
- [Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications](https://mlsanity.com/paper/2605.25303/) (2026)

## Abstract (arXiv)

We develop a general framework to significantly reduce the degree of sum-of-squares proofs by introducing new variables. To illustrate the power of this framework, we use it to speed up previous algorithms based on sum-of-squares for two important estimation problems, clustering and robust moment estimation. The resulting algorithms offer the same statistical guarantees as the previous best algorithms but have significantly faster running times. Roughly speaking, given a sample of n points in dimension d, our algorithms can exploit order-ℓ moments in time dO(ℓ)· nO(1), whereas a naive implementation requires time (d· n)O(ℓ). Since for the aforementioned applications, the typical sample size is dTheta(ℓ), our framework improves running times from dO(ℓ2) to dO(ℓ).