David Steurer

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 68

Top Venues

Publications

Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
Semirandom Planted Clique and the Restricted Isometry Property. CoRR (2024)
Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer
Private graphon estimation via sum-of-squares. CoRR (2024)
Hongjie Chen, Jingqiu Ding, Yiding Hua, David Steurer
Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust. CoRR (2024)
Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang
Robust Mixture Learning when Outliers Overwhelm Small Groups. CoRR (2024)
Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer
Private Graphon Estimation via Sum-of-Squares. STOC (2024)
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
Higher degree sum-of-squares relaxations robust against oblivious outliers. SODA (2023)
Yiding Hua, Jingqiu Ding, Tommaso d'Orsi, David Steurer
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. COLT (2023)
Gleb Novikov, David Steurer, Stefan Tiegel
Robust Mean Estimation Without a Mean: Dimension-Independent Error in Polynomial Time for Symmetric Distributions. CoRR (2023)
Gleb Novikov, David Steurer, Stefan Tiegel
Robust Mean Estimation Without Moments for Symmetric Distributions. NeurIPS (2023)
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
Private estimation algorithms for stochastic block models and mixture models. NeurIPS (2023)
Rares-Darius Buhai, David Steurer
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. COLT (2023)
Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
Private estimation algorithms for stochastic block models and mixture models. CoRR (2023)
Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, David Steurer
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. CoRR (2023)
Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
Algorithms Approaching the Threshold for Semi-random Planted Clique. STOC (2023)
Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
Algorithms approaching the threshold for semi-random planted clique. CoRR (2022)
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, Stefan Tiegel, David Steurer
Fast algorithm for overcomplete order-3 tensor decomposition. CoRR (2022)
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
Higher degree sum-of-squares relaxations robust against oblivious outliers. CoRR (2022)
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel
Fast algorithm for overcomplete order-3 tensor decomposition. COLT (2022)
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
Robust recovery for stochastic block models. FOCS (2022)
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
Robust recovery for stochastic block models. CoRR (2021)
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. NeurIPS (2021)
David Steurer, Stefan Tiegel
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. SODA (2021)
David Steurer, Stefan Tiegel
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. CoRR (2021)
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. CoRR (2021)
Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer
Playing unique games on certified small-set expanders. STOC (2021)
Tommaso d'Orsi, Gleb Novikov, David Steurer
Consistent regression when oblivious outliers overwhelm. ICML (2021)
Rares-Darius Buhai, David Steurer
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. CoRR (2021)
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
Robust recovery for stochastic block models. FOCS (2021)
Jingqiu Ding, Samuel B. Hopkins, David Steurer
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. NeurIPS (2020)
Tommaso d'Orsi, Gleb Novikov, David Steurer
Regress Consistently when Oblivious Outliers Overwhelm. CoRR (2020)
Jingqiu Ding, Samuel B. Hopkins, David Steurer
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. CoRR (2020)
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. CoRR (2020)
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. FOCS (2020)
Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
Playing Unique Games on Certified Small-Set Expanders. CoRR (2020)
Boaz Barak, Pravesh K. Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS (2019)
Prasad Raghavendra, Tselil Schramm, David Steurer
High-dimensional estimation via sum-of-squares proofs. CoRR (2018)
Boaz Barak, Pravesh Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. 25 (2018)
Boaz Barak, Pravesh K. Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR (2018)
Pravesh K. Kothari, Jacob Steinhardt, David Steurer
Robust moment estimation and improved clustering via sum of squares. STOC (2018)
Boaz Barak, Pravesh K. Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. STOC (2017)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The power of sum-of-squares for detecting hidden structures. CoRR (2017)
Aaron Potechin, David Steurer
Exact tensor completion with sum-of-squares. CoRR (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. CoRR (2017)
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS (2017)
Samuel B. Hopkins, David Steurer
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. FOCS (2017)
Tselil Schramm, David Steurer
Fast and robust tensor decomposition with applications to dictionary learning. COLT (2017)
Tselil Schramm, David Steurer
Fast and robust tensor decomposition with applications to dictionary learning. CoRR (2017)
Aaron Potechin, David Steurer
Exact tensor completion with sum-of-squares. COLT (2017)
Samuel B. Hopkins, David Steurer
Bayesian estimation from few samples: community detection and related problems. CoRR (2017)
Pravesh K. Kothari, David Steurer
Outlier-robust moment-estimation via sum-of-squares. CoRR (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. 24 (2017)
Tengyu Ma, Jonathan Shi, David Steurer
Polynomial-Time Tensor Decompositions with Sum-of-Squares. FOCS (2016)
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. STOC (2016)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM 63 (4) (2016)
Tengyu Ma, Jonathan Shi, David Steurer
Polynomial-time Tensor Decompositions with Sum-of-Squares. CoRR (2016)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. STOC (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Adam N. Letchford, Jean B. Lasserre, Pablo A. Parrilo, David Steurer
The 2013 Newton Institute Programme on polynomial optimization. Math. Program. 151 (2) (2015)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. SIAM J. Comput. 44 (5) (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Irit Dinur, David Steurer, Thomas Vidick
A parallel repetition theorem for entangled projection games. Comput. Complex. 24 (2) (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Samuel B. Hopkins, Jonathan Shi, David Steurer
Tensor principal component analysis via sum-of-square proofs. COLT (2015)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
Approximation Limits of Linear Programs (Beyond Hierarchies). Math. Oper. Res. 40 (3) (2015)
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
Speeding up sum-of-squares for tensor decomposition and planted sparse vectors. CoRR (2015)
Sanjeev Arora, Boaz Barak, David Steurer
Subexponential Algorithms for Unique Games and Related Problems. J. ACM 62 (5) (2015)
Samuel B. Hopkins, Jonathan Shi, David Steurer
Tensor principal component analysis via sum-of-squares proofs. CoRR (2015)
James R. Lee, Prasad Raghavendra, David Steurer
Lower Bounds on the Size of Semidefinite Programming Relaxations. STOC (2015)
Boaz Barak, Jonathan A. Kelner, David Steurer
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. CoRR (2014)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding sum-of-squares relaxations. STOC (2014)
Irit Dinur, David Steurer
Direct Product Testing. Computational Complexity Conference (2014)
Irit Dinur, David Steurer, Thomas Vidick
A Parallel Repetition Theorem for Entangled Projection Games. Computational Complexity Conference (2014)
Irit Dinur, David Steurer
Analytical approach to parallel repetition. STOC (2014)
Boaz Barak, David Steurer
Sum-of-squares proofs and the quest toward optimal algorithms. CoRR (2014)
James R. Lee, Prasad Raghavendra, David Steurer
Lower bounds on the size of semidefinite programming relaxations. CoRR (2014)
James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan
On the Power of Symmetric LP and SDP Relaxations. Computational Complexity Conference (2014)
Boaz Barak, David Steurer
Sum-of-squares proofs and the quest toward optimal algorithms. Electron. Colloquium Comput. Complex. 21 (2014)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. CoRR (2013)
Irit Dinur, David Steurer
Direct Product Testing. Electron. Colloquium Comput. Complex. 20 (2013)
Boaz Barak, Jonathan A. Kelner, David Steurer
Rounding Sum-of-Squares Relaxations. Electron. Colloquium Comput. Complex. 20 (2013)
Boaz Barak, Guy Kindler, David Steurer
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. ITCS (2013)
Irit Dinur, David Steurer, Thomas Vidick
A parallel repetition theorem for entangled projection games. CoRR (2013)
Irit Dinur, David Steurer
Analytical Approach to Parallel Repetition CoRR (2013)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. FOCS (2013)
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. CoRR (2013)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
Approximation Limits of Linear Programs (Beyond Hierarchies) CoRR (2012)
Sanjeev Arora, Constantinos Daskalakis, David Steurer
Message-Passing Algorithms and Improved LP Decoding. IEEE Trans. Inf. Theory 58 (12) (2012)
Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
Approximation Limits of Linear Programs (Beyond Hierarchies). FOCS (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, sum-of-squares proofs, and their applications. STOC (2012)
Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
Hypercontractivity, Sum-of-Squares Proofs, and their Applications CoRR (2012)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. FOCS (2012)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions between Expansion Problems. Computational Complexity Conference (2012)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. Electron. Colloquium Comput. Complex. 18 (2011)
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
Subsampling Mathematical Relaxations and Average-case Complexity. SODA (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture CoRR (2011)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. 18 (2011)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. FOCS (2011)
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
Finding Almost-Perfect Graph Bisections. ICS (2011)
Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation CoRR (2011)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions Between Expansion Problems CoRR (2010)

David Steurer.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

David Steurer