David Steurer - RankMe

136 papers A* 50A 7B 2Journal 72Unranked 4

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Faster MAX-CUT on Bounded Threshold Rank Graphs. CoRR Prashanti Anderson, Sam Hopkins, Amit Rajaraman, David Steurer
2025	A*	`conf`	Finding Colorings in One-Sided Expanders. FOCS Rares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-Kakas
2025	J	`jnl`	Finding Colorings in One-Sided Expanders. CoRR Rares-Darius Buhai, Yiding Hua, David Steurer, Andor Vári-Kakas
2025	J	`jnl`	Hesse's Redemption: Efficient Convex Polynomial Programming. CoRR Lucas Slot, David Steurer, Manuel Wiedmer
2025	J	`jnl`	Low degree conjecture implies sharp computational thresholds in stochastic block model. CoRR Jingqiu Ding, Yiding Hua, Lucas Slot, David Steurer
2025	A*	`conf`	Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares. SODA Hongjie Chen, Deepak Narayanan Sridharan, David Steurer
2025	J	`jnl`	Rate-optimal community detection near the KS threshold via node-robust algorithms. CoRR Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko
2024	J	`jnl`	Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures. CoRR Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2024	J	`jnl`	Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares. CoRR Hongjie Chen, Deepak Narayanan Sridharan, David Steurer
2024	A*	`conf`	Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust. NeurIPS Hongjie Chen, Jingqiu Ding, Yiding Hua, David Steurer
2024	J	`jnl`	Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust. CoRR Hongjie Chen, Jingqiu Ding, Yiding Hua, David Steurer
2024	A*	`conf`	Private Graphon Estimation via Sum-of-Squares. STOC Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer
2024	J	`jnl`	Private graphon estimation via sum-of-squares. CoRR Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer
2024	A*	`conf`	Robust Mixture Learning when Outliers Overwhelm Small Groups. NeurIPS Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang
2024	J	`jnl`	Robust Mixture Learning when Outliers Overwhelm Small Groups. CoRR Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang
2024	A*	`conf`	Semirandom Planted Clique and the Restricted Isometry Property. FOCS Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2024	J	`jnl`	Semirandom Planted Clique and the Restricted Isometry Property. CoRR Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2023	A*	`conf`	Algorithms Approaching the Threshold for Semi-random Planted Clique. STOC Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2023	A*	`conf`	Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. COLT Rares-Darius Buhai, David Steurer
2023	A*	`conf`	Higher degree sum-of-squares relaxations robust against oblivious outliers. SODA Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
2023	A*	`conf`	Private estimation algorithms for stochastic block models and mixture models. NeurIPS Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
2023	J	`jnl`	Private estimation algorithms for stochastic block models and mixture models. CoRR Hongjie Chen, Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto, Jacob Imola, David Steurer, Stefan Tiegel
2023	A*	`conf`	Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. COLT Yiding Hua, Jingqiu Ding, Tommaso d'Orsi, David Steurer
2023	J	`jnl`	Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. CoRR Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, David Steurer
2023	A*	`conf`	Robust Mean Estimation Without Moments for Symmetric Distributions. NeurIPS Gleb Novikov, David Steurer, Stefan Tiegel
2023	J	`jnl`	Robust Mean Estimation Without a Mean: Dimension-Independent Error in Polynomial Time for Symmetric Distributions. CoRR Gleb Novikov, David Steurer, Stefan Tiegel
2022	J	`jnl`	Algorithms approaching the threshold for semi-random planted clique. CoRR Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2022	A*	`conf`	Fast algorithm for overcomplete order-3 tensor decomposition. COLT Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, David Steurer, Stefan Tiegel
2022	J	`jnl`	Fast algorithm for overcomplete order-3 tensor decomposition. CoRR Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu, Stefan Tiegel, David Steurer
2022	J	`jnl`	Higher degree sum-of-squares relaxations robust against oblivious outliers. CoRR Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, David Steurer
2021	J	`jnl`	Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. CoRR Rares-Darius Buhai, David Steurer
2021	A*	`conf`	Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. NeurIPS Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
2021	J	`jnl`	Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. CoRR Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, Stefan Tiegel
2021	A*	`conf`	Consistent regression when oblivious outliers overwhelm. ICML Tommaso d'Orsi, Gleb Novikov, David Steurer
2021	A*	`conf`	Playing unique games on certified small-set expanders. STOC Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer
2021	A*	`conf`	Robust recovery for stochastic block models. FOCS Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
2021	J	`jnl`	Robust recovery for stochastic block models. CoRR Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
2021	A*	`conf`	SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. SODA David Steurer, Stefan Tiegel
2021	J	`jnl`	SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. CoRR David Steurer, Stefan Tiegel
2020	A*	`conf`	Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. NeurIPS Jingqiu Ding, Samuel B. Hopkins, David Steurer
2020	J	`jnl`	Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. CoRR Jingqiu Ding, Samuel B. Hopkins, David Steurer
2020	J	`jnl`	Playing Unique Games on Certified Small-Set Expanders. CoRR Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
2020	J	`jnl`	Regress Consistently when Oblivious Outliers Overwhelm. CoRR Tommaso d'Orsi, Gleb Novikov, David Steurer
2020	A*	`conf`	Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. FOCS Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
2020	J	`jnl`	Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. CoRR Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
2019	A	`conf`	Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS Boaz Barak, Pravesh K. Kothari, David Steurer
2018	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, Princeton, NJ, USA, August 20-22, 2018 APPROX-RANDOM Eric Blais, Klaus Jansen, José D. P. Rolim, David Steurer
2018	J	`jnl`	High-dimensional estimation via sum-of-squares proofs. CoRR Prasad Raghavendra, Tselil Schramm, David Steurer
2018	A*	`conf`	Robust moment estimation and improved clustering via sum of squares. STOC Pravesh K. Kothari, Jacob Steinhardt, David Steurer
2018	J	`jnl`	Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR Boaz Barak, Pravesh K. Kothari, David Steurer
2018	J	`jnl`	Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. Boaz Barak, Pravesh Kothari, David Steurer
2017	J	`jnl`	Bayesian estimation from few samples: community detection and related problems. CoRR Samuel B. Hopkins, David Steurer
2017	A*	`conf`	Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. FOCS Samuel B. Hopkins, David Steurer
2017	A*	`conf`	Exact tensor completion with sum-of-squares. COLT Aaron Potechin, David Steurer
2017	J	`jnl`	Exact tensor completion with sum-of-squares. CoRR Aaron Potechin, David Steurer
2017	A*	`conf`	Fast and robust tensor decomposition with applications to dictionary learning. COLT Tselil Schramm, David Steurer
2017	J	`jnl`	Fast and robust tensor decomposition with applications to dictionary learning. CoRR Tselil Schramm, David Steurer
2017	J	`jnl`	Outlier-robust moment-estimation via sum-of-squares. CoRR Pravesh K. Kothari, David Steurer
2017	A*	`conf`	Quantum entanglement, sum of squares, and the log rank conjecture. STOC Boaz Barak, Pravesh K. Kothari, David Steurer
2017	J	`jnl`	Quantum entanglement, sum of squares, and the log rank conjecture. CoRR Boaz Barak, Pravesh Kothari, David Steurer
2017	J	`jnl`	Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. Boaz Barak, Pravesh Kothari, David Steurer
2017	A*	`conf`	The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2017	J	`jnl`	The power of sum-of-squares for detecting hidden structures. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2016	J	`jnl`	Approximate Constraint Satisfaction Requires Large LP Relaxations. J. ACM Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2016	A*	`conf`	Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. STOC Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
2016	A*	`conf`	Polynomial-Time Tensor Decompositions with Sum-of-Squares. FOCS Tengyu Ma, Jonathan Shi, David Steurer
2016	J	`jnl`	Polynomial-time Tensor Decompositions with Sum-of-Squares. CoRR Tengyu Ma, Jonathan Shi, David Steurer
2015	J	`jnl`	A parallel repetition theorem for entangled projection games. Comput. Complex. Irit Dinur, David Steurer, Thomas Vidick
2015	J	`jnl`	Approximation Limits of Linear Programs (Beyond Hierarchies). Math. Oper. Res. Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
2015	—	`conf`	Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	A*	`conf`	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. STOC Boaz Barak, Jonathan A. Kelner, David Steurer
2015	A*	`conf`	Lower Bounds on the Size of Semidefinite Programming Relaxations. STOC James R. Lee, Prasad Raghavendra, David Steurer
2015	J	`jnl`	Making the Long Code Shorter. SIAM J. Comput. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2015	J	`jnl`	Speeding up sum-of-squares for tensor decomposition and planted sparse vectors. CoRR Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer
2015	J	`jnl`	Subexponential Algorithms for Unique Games and Related Problems. J. ACM Sanjeev Arora, Boaz Barak, David Steurer
2015	A*	`conf`	Tensor principal component analysis via sum-of-square proofs. COLT Samuel B. Hopkins, Jonathan Shi, David Steurer
2015	J	`jnl`	Tensor principal component analysis via sum-of-squares proofs. CoRR Samuel B. Hopkins, Jonathan Shi, David Steurer
2015	J	`jnl`	The 2013 Newton Institute Programme on polynomial optimization. Math. Program. Adam N. Letchford, Jean B. Lasserre, Pablo A. Parrilo, David Steurer
2014	A	`conf`	A Parallel Repetition Theorem for Entangled Projection Games. CCC Irit Dinur, David Steurer, Thomas Vidick
2014	A*	`conf`	Analytical approach to parallel repetition. STOC Irit Dinur, David Steurer
2014	J	`jnl`	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. CoRR Boaz Barak, Jonathan A. Kelner, David Steurer
2014	A	`conf`	Direct Product Testing. CCC Irit Dinur, David Steurer
2014	J	`jnl`	Lower bounds on the size of semidefinite programming relaxations. CoRR James R. Lee, Prasad Raghavendra, David Steurer
2014	A	`conf`	On the Power of Symmetric LP and SDP Relaxations. CCC James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan
2014	A*	`conf`	Rounding sum-of-squares relaxations. STOC Boaz Barak, Jonathan A. Kelner, David Steurer
2014	J	`jnl`	Sum-of-squares proofs and the quest toward optimal algorithms. CoRR Boaz Barak, David Steurer
2014	J	`jnl`	Sum-of-squares proofs and the quest toward optimal algorithms. Electron. Colloquium Comput. Complex. Boaz Barak, David Steurer
2013	J	`jnl`	A parallel repetition theorem for entangled projection games. CoRR Irit Dinur, David Steurer, Thomas Vidick
2013	J	`jnl`	Analytical Approach to Parallel Repetition CoRR Irit Dinur, David Steurer
2013	A*	`conf`	Approximate Constraint Satisfaction Requires Large LP Relaxations. FOCS Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013	J	`jnl`	Approximate Constraint Satisfaction Requires Large LP Relaxations. CoRR Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
2013	J	`jnl`	Direct Product Testing. Electron. Colloquium Comput. Complex. Irit Dinur, David Steurer
2013	A	`conf`	On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. ITCS Boaz Barak, Guy Kindler, David Steurer
2013	J	`jnl`	Rounding Sum-of-Squares Relaxations. CoRR Boaz Barak, Jonathan A. Kelner, David Steurer
2013	J	`jnl`	Rounding Sum-of-Squares Relaxations. Electron. Colloquium Comput. Complex. Boaz Barak, Jonathan A. Kelner, David Steurer
2012	J	`jnl`	Approximation Limits of Linear Programs (Beyond Hierarchies) CoRR Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
2012	A*	`conf`	Approximation Limits of Linear Programs (Beyond Hierarchies). FOCS Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
2012	J	`jnl`	Hypercontractivity, Sum-of-Squares Proofs, and their Applications CoRR Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
2012	A*	`conf`	Hypercontractivity, sum-of-squares proofs, and their applications. STOC Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, Yuan Zhou
2012	A*	`conf`	Making the Long Code Shorter. FOCS Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2012	J	`jnl`	Message-Passing Algorithms and Improved LP Decoding. IEEE Trans. Inf. Theory Sanjeev Arora, Constantinos Daskalakis, David Steurer
2012	A	`conf`	Reductions between Expansion Problems. CCC Prasad Raghavendra, David Steurer, Madhur Tulsiani
2011	A	`conf`	Finding Almost-Perfect Graph Bisections. ICS Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
2011	J	`jnl`	Making the long code shorter, with applications to the Unique Games Conjecture CoRR Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Making the long code shorter, with applications to the Unique Games Conjecture. Electron. Colloquium Comput. Complex. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Rounding Semidefinite Programming Hierarchies via Global Correlation CoRR Boaz Barak, Prasad Raghavendra, David Steurer
2011	A*	`conf`	Rounding Semidefinite Programming Hierarchies via Global Correlation. FOCS Boaz Barak, Prasad Raghavendra, David Steurer
2011	J	`jnl`	Rounding Semidefinite Programming Hierarchies via Global Correlation. Electron. Colloquium Comput. Complex. Boaz Barak, Prasad Raghavendra, David Steurer
2011	A*	`conf`	Subsampling Mathematical Relaxations and Average-case Complexity. SODA Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
2010	A*	`conf`	Approximations for the isoperimetric and spectral profile of graphs and related parameters. STOC Prasad Raghavendra, David Steurer, Prasad Tetali
2010	A*	`conf`	Fast SDP Algorithms for Constraint Satisfaction Problems. SODA David Steurer
2010	A*	`conf`	Graph expansion and the unique games conjecture. STOC Prasad Raghavendra, David Steurer
2010	J	`jnl`	Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer
2010	—	`conf`	Improved Rounding for Parallel Repeated Unique Games. APPROX-RANDOM David Steurer
2010	J	`jnl`	Reductions Between Expansion Problems CoRR Prasad Raghavendra, David Steurer, Madhur Tulsiani
2010	J	`jnl`	Reductions Between Expansion Problems. Electron. Colloquium Comput. Complex. Prasad Raghavendra, David Steurer, Madhur Tulsiani
2010	A*	`conf`	Subexponential Algorithms for Unique Games and Related Problems. FOCS Sanjeev Arora, Boaz Barak, David Steurer
2009	J	`jnl`	Connections Between Unique Games and Multicut. Electron. Colloquium Comput. Complex. David Steurer, Nisheeth K. Vishnoi
2009	A*	`conf`	How to Round Any CSP. FOCS Prasad Raghavendra, David Steurer
2009	A*	`conf`	Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. FOCS Prasad Raghavendra, David Steurer
2009	A*	`conf`	Message passing algorithms and improved LP decoding. STOC Sanjeev Arora, Constantinos Daskalakis, David Steurer
2009	J	`jnl`	Subsampling Semidefinite Programs and Max-Cut on the Sphere CoRR Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
2009	J	`jnl`	Subsampling Semidefinite Programs and Max-Cut on the Sphere. Electron. Colloquium Comput. Complex. Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer
2009	—	`conf`	Towards a Study of Low-Complexity Graphs. ICALP (1) Sanjeev Arora, David Steurer, Avi Wigderson
2009	A*	`conf`	Towards computing the Grothendieck constant. SODA Prasad Raghavendra, David Steurer
2008	J	`jnl`	An asymptotic approximation scheme for multigraph edge coloring. ACM Trans. Algorithms Peter Sanders, David Steurer
2008	—	`conf`	Asymptotically Optimal Hitting Sets Against Polynomials. ICALP (1) Markus Bläser, Moritz Hardt, David Steurer
2008	A*	`conf`	Rounding Parallel Repetitions of Unique Games. FOCS Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer
2008	A*	`conf`	Unique games on expanding constraint graphs are easy: extended abstract. STOC Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi
2007	J	`jnl`	The Interval Liar Game. Electron. Notes Discret. Math. Benjamin Doerr, Johannes Lengler, David Steurer
2006	B	`conf`	The Interval Liar Game. ISAAC Benjamin Doerr, Johannes Lengler, David Steurer
2006	J	`jnl`	Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted Graphs CoRR David Steurer
2006	B	`conf`	Tight bounds for the Min-Max boundary decomposition cost of weighted graphs. SPAA David Steurer
2005	A*	`conf`	An asymptotic approximation scheme for multigraph edge coloring. SODA Peter Sanders, David Steurer