David Steurer

According to our database, David Steurer authored at least 71 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Private graphon estimation via sum-of-squares.

Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer

CoRR, 2024

2023

Robust Mean Estimation Without a Mean: Dimension-Independent Error in Polynomial Time for Symmetric Distributions.

Gleb Novikov, David Steurer, Stefan Tiegel

CoRR, 2023

Algorithms Approaching the Threshold for Semi-random Planted Clique.

Rares-Darius Buhai, Pravesh K. Kothari, David Steurer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Higher degree sum-of-squares relaxations robust against oblivious outliers.

Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Robust Mean Estimation Without Moments for Symmetric Distributions.

Gleb Novikov, David Steurer, Stefan Tiegel

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Private estimation algorithms for stochastic block models and mixture models.

Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions.

Yiding Hua, Jingqiu Ding, Tommaso d'Orsi, David Steurer

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures.

Rares-Darius Buhai, David Steurer

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Fast algorithm for overcomplete order-3 tensor decomposition.

Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Playing unique games on certified small-set expanders.

Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

David Steurer, Stefan Tiegel

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers.

Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Consistent regression when oblivious outliers overwhelm.

Tommaso d'Orsi, Gleb Novikov, David Steurer

Proceedings of the 38th International Conference on Machine Learning, 2021

Robust recovery for stochastic block models.

Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Regress Consistently when Oblivious Outliers Overwhelm.

Tommaso d'Orsi, Gleb Novikov, David Steurer

CoRR, 2020

Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks.

Jingqiu Ding, Samuel B. Hopkins, David Steurer

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates.

Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2018

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture.

Boaz Barak, Pravesh Kothari, David Steurer

Electron. Colloquium Comput. Complex., 2018

High-dimensional estimation via sum-of-squares proofs.

Prasad Raghavendra, Tselil Schramm, David Steurer

CoRR, 2018

Robust moment estimation and improved clustering via sum of squares.

Pravesh K. Kothari, Jacob Steinhardt, David Steurer

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Quantum entanglement, sum of squares, and the log rank conjecture.

Boaz Barak, Pravesh Kothari, David Steurer

Electron. Colloquium Comput. Complex., 2017

Outlier-robust moment-estimation via sum-of-squares.

Pravesh K. Kothari, David Steurer

CoRR, 2017

Bayesian estimation from few samples: community detection and related problems.

Samuel B. Hopkins, David Steurer

CoRR, 2017

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems.

Samuel B. Hopkins, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fast and robust tensor decomposition with applications to dictionary learning.

Tselil Schramm, David Steurer

Proceedings of the 30th Conference on Learning Theory, 2017

Exact tensor completion with sum-of-squares.

Aaron Potechin, David Steurer

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Approximate Constraint Satisfaction Requires Large LP Relaxations.

Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer

J. ACM, 2016

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Polynomial-Time Tensor Decompositions with Sum-of-Squares.

Tengyu Ma, Jonathan Shi, David Steurer

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Making the Long Code Shorter.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

SIAM J. Comput., 2015

The 2013 Newton Institute Programme on polynomial optimization.

Adam N. Letchford, Jean B. Lasserre, Pablo A. Parrilo, David Steurer

Math. Program., 2015

Approximation Limits of Linear Programs (Beyond Hierarchies).

Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer

Math. Oper. Res., 2015

Subexponential Algorithms for Unique Games and Related Problems.

Sanjeev Arora, Boaz Barak, David Steurer

J. ACM, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Speeding up sum-of-squares for tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

CoRR, 2015

Tensor principal component analysis via sum-of-squares proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

CoRR, 2015

A parallel repetition theorem for entangled projection games.

Irit Dinur, David Steurer, Thomas Vidick

Comput. Complex., 2015

Lower Bounds on the Size of Semidefinite Programming Relaxations.

James R. Lee, Prasad Raghavendra, David Steurer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.

Boaz Barak, Jonathan A. Kelner, David Steurer

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Tensor principal component analysis via sum-of-square proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Sum-of-squares proofs and the quest toward optimal algorithms.

Boaz Barak, David Steurer

Electron. Colloquium Comput. Complex., 2014

Analytical approach to parallel repetition.

Irit Dinur, David Steurer

Proceedings of the Symposium on Theory of Computing, 2014

On the Power of Symmetric LP and SDP Relaxations.

James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Direct Product Testing.

Irit Dinur, David Steurer

Electron. Colloquium Comput. Complex., 2013

Rounding Sum-of-Squares Relaxations.

Boaz Barak, Jonathan A. Kelner, David Steurer

Electron. Colloquium Comput. Complex., 2013

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.

Boaz Barak, Guy Kindler, David Steurer

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Message-Passing Algorithms and Improved LP Decoding.

Sanjeev Arora, Constantinos Daskalakis, David Steurer

IEEE Trans. Inf. Theory, 2012

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

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

Boaz Barak, Prasad Raghavendra, David Steurer

Electron. Colloquium Comput. Complex., 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

Subsampling Mathematical Relaxations and Average-case Complexity.

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Finding Almost-Perfect Graph Bisections.

Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou

Proceedings of the Innovations in Computer Science, 2011

2010

Reductions Between Expansion Problems.

Prasad Raghavendra, David Steurer, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2010

Improved Algorithms for Unique Games via Divide and Conquer.

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

Electron. Colloquium Comput. Complex., 2010

Approximations for the isoperimetric and spectral profile of graphs and related parameters.

Prasad Raghavendra, David Steurer, Prasad Tetali

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Graph expansion and the unique games conjecture.

Prasad Raghavendra, David Steurer

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Fast SDP Algorithms for Constraint Satisfaction Problems.

David Steurer

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Improved Rounding for Parallel Repeated Unique Games.

David Steurer

Proceedings of the Approximation, 2010

2009

Connections Between Unique Games and Multicut.

David Steurer, Nisheeth K. Vishnoi

Electron. Colloquium Comput. Complex., 2009

Subsampling Semidefinite Programs and Max-Cut on the Sphere.

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

Electron. Colloquium Comput. Complex., 2009

Towards computing the Grothendieck constant.

Prasad Raghavendra, David Steurer

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Towards a Study of Low-Complexity Graphs.

Sanjeev Arora, David Steurer, Avi Wigderson

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

How to Round Any CSP.

Prasad Raghavendra, David Steurer

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES.

Prasad Raghavendra, David Steurer

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

An asymptotic approximation scheme for multigraph edge coloring.

Peter Sanders, David Steurer

ACM Trans. Algorithms, 2008

Unique games on expanding constraint graphs are easy: extended abstract.

Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Asymptotically Optimal Hitting Sets Against Polynomials.

Markus Bläser, Moritz Hardt, David Steurer

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Rounding Parallel Repetitions of Unique Games.

Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

The Interval Liar Game.

Benjamin Doerr, Johannes Lengler, David Steurer

Electron. Notes Discret. Math., 2007

2006

Tight bounds for the Min-Max boundary decomposition cost of weighted graphs.

David Steurer

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006