Steurer, David
- Analytical Approach to Parallel Repetition
2013/05/09 by Irit Dinur, David Steurer, Dinur, Irit +1 · 12 citations
Computer Science · #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
- The power of sum-of-squares for detecting hidden structures
2017/10/13 by Hopkins, Samuel B., Kothari, Pravesh K., Potechin, Aaron +3 · 10 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Beating the random assignment on constraint satisfaction problems of bounded degree
2015/05/13 by Boaz Barak, Barak, Boaz, Ankur Moitra +17 · 3 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms
- Rounding Semidefinite Programming Hierarchies via Global Correlation
2011/04/25 by Barak, Boaz, Raghavendra, Prasad, Steurer, David · 3 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Tensor principal component analysis via sum-of-squares proofs
2015/07/12 by Hopkins, Samuel B., Shi, Jonathan, Steurer, David · 3 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Polynomial-time Tensor Decompositions with Sum-of-Squares
2016/10/06 by Ma, Tengyu, Shi, Jonathan, Steurer, David · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
- Bayesian estimation from few samples: community detection and related\n problems
2017/09/30 by Samuel B. Hopkins, David Steurer, Hopkins, Samuel B. +1 · 5 citations
Mathematics · #Statistical Methods and Bayesian Inference #Advanced Causal Inference Techniques #Markov Chains and Monte Carlo Methods
- A parallel repetition theorem for entangled projection games
2013/10/15 by Dinur, Irit, Steurer, David, Vidick, Thomas · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
- Sum-of-squares proofs and the quest toward optimal algorithms
2014/04/21 by Barak, Boaz, Steurer, David · 3 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
- Dictionary Learning and Tensor Decomposition via the Sum-of-Squares\n Method
2014/07/06 by Boaz Barak, Jonathan A. Kelner, Barak, Boaz +3 · 2 citations
Computer Science · Engineering · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #F.2.1 #F.2.2 #FOS: Computer and information sciences #I.2.6 #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
2015/12/08 by Hopkins, Samuel B., Schramm, Tselil, Shi, Jonathan +1 · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Exact tensor completion with sum-of-squares
2017/02/21 by Aaron Potechin, David Steurer, Potechin, Aaron +1 · 2 citations
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel Computing and Optimization Techniques #Polynomial and algebraic computation #Tensor decomposition and applications
- Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
2018/04/23 by Barak, Boaz, Kothari, Pravesh K., Steurer, David · 2 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
- High-dimensional estimation via sum-of-squares proofs
2018/07/30 by Raghavendra, Prasad, Schramm, Tselil, Steurer, David · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Consistent Estimation for PCA and Sparse Regression with Oblivious\n Outliers
2021/11/04 by Tommaso d'Orsi, d'Orsi, Tommaso, Chih-Hung Liu +9 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
- Subsampling Mathematical Relaxations and Average-case Complexity
2009/11/29 by Barak, Boaz, Hardt, Moritz, Holenstein, Thomas +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
- Approximation Limits of Linear Programs (Beyond Hierarchies)
2012/04/04 by Braun, Gábor, Fiorini, Samuel, Pokutta, Sebastian +1 · 1 citation
#68W25 #90C05 #90C60 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
- Approximate Constraint Satisfaction Requires Large LP Relaxations
2013/09/03 by Chan, Siu On, Lee, James R., Raghavendra, Prasad +1 · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
- Outlier-robust moment-estimation via sum-of-squares
2017/11/30 by Kothari, Pravesh K., Steurer, David · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Consistent regression when oblivious outliers overwhelm
2020/09/30 by d'Orsi, Tommaso, Novikov, Gleb, Steurer, David · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
2020/11/12 by d'Orsi, Tommaso, Kothari, Pravesh K., Novikov, Gleb +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
- Higher degree sum-of-squares relaxations robust against oblivious outliers
2022/11/14 by d'Orsi, Tommaso, Nasser, Rajai, Novikov, Gleb +1 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Private estimation algorithms for stochastic block models and mixture models
2023/01/11 by Chen, Hongjie, Cohen-Addad, Vincent, d'Orsi, Tommaso +4 · 1 citation
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
- Algorithms approaching the threshold for semi-random planted clique
2022/12/11 by Rares-Darius Buhai, Buhai, Rares-Darius, Pravesh K. Kothari +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Random Matrices and Applications #Stochastic processes and statistical mechanics
- Low degree conjecture implies sharp computational thresholds in stochastic block model
2025/02/20 by Ding, Jingqiu, Hua, Yiding, Slot, Lucas +1 · 2 citations
#Computation (stat.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)
- Semirandom Planted Clique and the Restricted Isometry Property
2024/04/22 by Błasiok, Jarosław, Buhai, Rares-Darius, Kothari, Pravesh K. +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences