Tight bounds for the Min-Max boundary decomposition cost of weighted graphs. - David Steurer (SPAA, 2006)

The Interval Liar Game. - Benjamin Doerr; Johannes Lengler; David Steurer (Electron. Notes Discret. Math., 2007)

Rounding Parallel Repetitions of Unique Games. - Boaz Barak; Moritz Hardt; Ishay Haviv; Anup Rao 001; Oded Regev 001; David Steurer (FOCS, 2008)

Asymptotically Optimal Hitting Sets Against Polynomials. - Markus Bläser; Moritz Hardt; David Steurer (ICALP (1), 2008)

Unique games on expanding constraint graphs are easy: extended abstract. - Sanjeev Arora; Subhash Khot; Alexandra Kolla; David Steurer; Madhur Tulsiani; Nisheeth K. Vishnoi (STOC, 2008)

An asymptotic approximation scheme for multigraph edge coloring. - Peter Sanders 001; David Steurer (ACM Trans. Algorithms, 2008)

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. - Prasad Raghavendra; David Steurer (FOCS, 2009)

How to Round Any CSP. - Prasad Raghavendra; David Steurer (FOCS, 2009)

Towards a Study of Low-Complexity Graphs. - Sanjeev Arora; David Steurer; Avi Wigderson (ICALP (1), 2009)

Towards computing the Grothendieck constant. - Prasad Raghavendra; David Steurer (SODA, 2009)

Subsampling Semidefinite Programs and Max-Cut on the Sphere. - Boaz Barak; Moritz Hardt; Thomas Holenstein; David Steurer (Electron. Colloquium Comput. Complex., 2009)

Connections Between Unique Games and Multicut. - David Steurer; Nisheeth K. Vishnoi (Electron. Colloquium Comput. Complex., 2009)

Improved Rounding for Parallel Repeated Unique Games. - David Steurer (APPROX-RANDOM, 2010)

Fast SDP Algorithms for Constraint Satisfaction Problems. - David Steurer (SODA, 2010)

Graph expansion and the unique games conjecture. - Prasad Raghavendra; David Steurer (STOC, 2010)

Approximations for the isoperimetric and spectral profile of graphs and related parameters. - Prasad Raghavendra; David Steurer; Prasad Tetali (STOC, 2010)

Improved Algorithms for Unique Games via Divide and Conquer. - Sanjeev Arora; Russell Impagliazzo; William Matthews; David Steurer (Electron. Colloquium Comput. Complex., 2010)

Reductions Between Expansion Problems. - Prasad Raghavendra; David Steurer; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2010)

Finding Almost-Perfect Graph Bisections. - Venkatesan Guruswami; Yury Makarychev; Prasad Raghavendra; David Steurer; Yuan Zhou 007 (ICS, 2011)

Subsampling Mathematical Relaxations and Average-case Complexity. - Boaz Barak; Moritz Hardt; Thomas Holenstein; David Steurer (SODA, 2011)

Making the long code shorter, with applications to the Unique Games Conjecture. - Boaz Barak; Parikshit Gopalan; Johan Håstad; Raghu Meka; Prasad Raghavendra; David Steurer (Electron. Colloquium Comput. Complex., 2011)

Rounding Semidefinite Programming Hierarchies via Global Correlation. - Boaz Barak; Prasad Raghavendra; David Steurer (Electron. Colloquium Comput. Complex., 2011)

Hypercontractivity, sum-of-squares proofs, and their applications. - Boaz Barak; Fernando G. S. L. Brandão; Aram W. Harrow; Jonathan A. Kelner; David Steurer; Yuan Zhou 007 (STOC, 2012)

Message-Passing Algorithms and Improved LP Decoding. - Sanjeev Arora; Constantinos Daskalakis; David Steurer (IEEE Trans. Inf. Theory, 2012)

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. - Boaz Barak; Guy Kindler; David Steurer (ITCS, 2013)

Rounding Sum-of-Squares Relaxations. - Boaz Barak; Jonathan A. Kelner; David Steurer (Electron. Colloquium Comput. Complex., 2013)

Direct Product Testing. - Irit Dinur; David Steurer (Electron. Colloquium Comput. Complex., 2013)

On the Power of Symmetric LP and SDP Relaxations. - James R. Lee; Prasad Raghavendra; David Steurer; Ning Tan 002 (CCC, 2014)

Analytical approach to parallel repetition. - Irit Dinur; David Steurer (STOC, 2014)

Sum-of-squares proofs and the quest toward optimal algorithms. - Boaz Barak; David Steurer (Electron. Colloquium Comput. Complex., 2014)

Tensor principal component analysis via sum-of-square proofs. - Samuel B. Hopkins 001; Jonathan Shi; David Steurer (COLT, 2015)

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. - Boaz Barak; Jonathan A. Kelner; David Steurer (STOC, 2015)

Lower Bounds on the Size of Semidefinite Programming Relaxations. - James R. Lee; Prasad Raghavendra; David Steurer (STOC, 2015)

A parallel repetition theorem for entangled projection games. - Irit Dinur; David Steurer; Thomas Vidick (Comput. Complex., 2015)

Tensor principal component analysis via sum-of-squares proofs. - Samuel B. Hopkins 001; Jonathan Shi; David Steurer (CoRR, 2015)

Speeding up sum-of-squares for tensor decomposition and planted sparse vectors. - Samuel B. Hopkins 001; Tselil Schramm; Jonathan Shi; David Steurer (CoRR, 2015)

Beating the random assignment on constraint satisfaction problems of bounded degree. - Boaz Barak; Ankur Moitra; Ryan O'Donnell; Prasad Raghavendra; Oded Regev 001; David Steurer; Luca Trevisan 001; Aravindan Vijayaraghavan; David Witmer; John Wright 004 (Electron. Colloquium Comput. Complex., 2015)

Subexponential Algorithms for Unique Games and Related Problems. - Sanjeev Arora; Boaz Barak; David Steurer (J. ACM, 2015)

Approximation Limits of Linear Programs (Beyond Hierarchies). - Gábor Braun; Samuel Fiorini; Sebastian Pokutta; David Steurer (Math. Oper. Res., 2015)

The 2013 Newton Institute Programme on polynomial optimization. - Adam N. Letchford; Jean B. Lasserre; Pablo A. Parrilo; David Steurer (Math. Program., 2015)

Making the Long Code Shorter. - Boaz Barak; Parikshit Gopalan; Johan Håstad; Raghu Meka; Prasad Raghavendra; David Steurer (SIAM J. Comput., 2015)

Polynomial-Time Tensor Decompositions with Sum-of-Squares. - Tengyu Ma 001; Jonathan Shi; David Steurer (FOCS, 2016)

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. - Samuel B. Hopkins 001; Tselil Schramm; Jonathan Shi; David Steurer (STOC, 2016)

Approximate Constraint Satisfaction Requires Large LP Relaxations. - Siu On Chan; James R. Lee; Prasad Raghavendra; David Steurer (J. ACM, 2016)

Exact tensor completion with sum-of-squares. - Aaron Potechin; David Steurer (COLT, 2017)

Fast and robust tensor decomposition with applications to dictionary learning. - Tselil Schramm; David Steurer (COLT, 2017)

The Power of Sum-of-Squares for Detecting Hidden Structures. - Samuel B. Hopkins 001; Pravesh K. Kothari; Aaron Potechin; Prasad Raghavendra; Tselil Schramm; David Steurer (FOCS, 2017)

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. - Samuel B. Hopkins 001; David Steurer (FOCS, 2017)

Bayesian estimation from few samples: community detection and related problems. - Samuel B. Hopkins 001; David Steurer (CoRR, 2017)

Outlier-robust moment-estimation via sum-of-squares. - Pravesh K. Kothari; David Steurer (CoRR, 2017)

Quantum entanglement, sum of squares, and the log rank conjecture. - Boaz Barak; Pravesh Kothari; David Steurer (Electron. Colloquium Comput. Complex., 2017)

Robust moment estimation and improved clustering via sum of squares. - Pravesh K. Kothari; Jacob Steinhardt; David Steurer (STOC, 2018)

High-dimensional estimation via sum-of-squares proofs. - Prasad Raghavendra; Tselil Schramm; David Steurer (CoRR, 2018)

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. - Boaz Barak; Pravesh Kothari; David Steurer (Electron. Colloquium Comput. Complex., 2018)

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. - Tommaso d'Orsi; Pravesh K. Kothari; Gleb Novikov; David Steurer (FOCS, 2020)

Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. - Jingqiu Ding; Samuel B. Hopkins 001; David Steurer (NeurIPS, 2020)

Regress Consistently when Oblivious Outliers Overwhelm. - Tommaso d'Orsi; Gleb Novikov; David Steurer (CoRR, 2020)

Robust recovery for stochastic block models. - Jingqiu Ding; Tommaso d'Orsi; Rajai Nasser; David Steurer (FOCS, 2021)

Consistent regression when oblivious outliers overwhelm. - Tommaso d'Orsi; Gleb Novikov; David Steurer (ICML, 2021)

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. - Tommaso d'Orsi; Chih-Hung Liu 001; Rajai Nasser; Gleb Novikov; David Steurer; Stefan Tiegel (NeurIPS, 2021)

SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. - David Steurer; Stefan Tiegel (SODA, 2021)

Playing unique games on certified small-set expanders. - Mitali Bafna; Boaz Barak; Pravesh K. Kothari; Tselil Schramm; David Steurer (STOC, 2021)

Fast algorithm for overcomplete order-3 tensor decomposition. - Jingqiu Ding; Tommaso d'Orsi; Chih-Hung Liu 001; David Steurer; Stefan Tiegel (COLT, 2022)

Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. - Rares-Darius Buhai; David Steurer (COLT, 2023)

Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. - Yiding Hua; Jingqiu Ding; Tommaso d'Orsi; David Steurer (COLT, 2023)

Private estimation algorithms for stochastic block models and mixture models. - Hongjie Chen 004; Vincent Cohen-Addad; Tommaso d'Orsi; Alessandro Epasto; Jacob Imola; David Steurer; Stefan Tiegel (NeurIPS, 2023)

Robust Mean Estimation Without Moments for Symmetric Distributions. - Gleb Novikov; David Steurer; Stefan Tiegel (NeurIPS, 2023)

Higher degree sum-of-squares relaxations robust against oblivious outliers. - Tommaso d'Orsi; Rajai Nasser; Gleb Novikov; David Steurer (SODA, 2023)

Algorithms Approaching the Threshold for Semi-random Planted Clique. - Rares-Darius Buhai; Pravesh K. Kothari; David Steurer (STOC, 2023)

Robust Mean Estimation Without a Mean: Dimension-Independent Error in Polynomial Time for Symmetric Distributions. - Gleb Novikov; David Steurer; Stefan Tiegel (CoRR, 2023)

Semirandom Planted Clique and the Restricted Isometry Property. - Jaroslaw Blasiok; Rares-Darius Buhai; Pravesh K. Kothari; David Steurer (FOCS, 2024)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust. - Hongjie Chen 004; Jingqiu Ding; Yiding Hua; David Steurer (NeurIPS, 2024)

Robust Mixture Learning when Outliers Overwhelm Small Groups. - Daniil Dmitriev; Rares-Darius Buhai; Stefan Tiegel; Alexander Wolters; Gleb Novikov; Amartya Sanyal; David Steurer; Fanny Yang (NeurIPS, 2024)

Private Graphon Estimation via Sum-of-Squares. - Hongjie Chen 004; Jingqiu Ding; Tommaso d'Orsi; Yiding Hua; Chih-Hung Liu 001; David Steurer (STOC, 2024)

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures. - Prashanti Anderson; Mitali Bafna; Rares-Darius Buhai; Pravesh K. Kothari; David Steurer (CoRR, 2024)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares. - Hongjie Chen 004; Deepak Narayanan Sridharan; David Steurer (SODA, 2025)

Low degree conjecture implies sharp computational thresholds in stochastic block model. - Jingqiu Ding; Yiding Hua; Lucas Slot; David Steurer (CoRR, 2025)

Finding Colorings in One-Sided Expanders. - Rares-Darius Buhai; Yiding Hua; David Steurer; Andor Vári-Kakas (CoRR, 2025)