# David Steurer

According to our database

Collaborative distances:

^{1}, David Steurer authored at least 49 papers between 2005 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

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

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Robust moment estimation and improved clustering via sum of squares.

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

2017

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

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

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

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

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

Fast and robust tensor decomposition with applications to dictionary learning.

Proceedings of the 30th Conference on Learning Theory, 2017

Exact tensor completion with sum-of-squares.

Proceedings of the 30th Conference on Learning Theory, 2017

2016

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

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

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

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

2015

The 2013 Newton Institute Programme on polynomial optimization.

Math. Program., 2015

Lower Bounds on the Size of Semidefinite Programming Relaxations.

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.

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

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

Proceedings of The 28th Conference on Learning Theory, 2015

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.

Proceedings of the Approximation, 2015

2014

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

Electronic Colloquium on Computational Complexity (ECCC), 2014

Analytical approach to parallel repetition.

Proceedings of the Symposium on Theory of Computing, 2014

Rounding sum-of-squares relaxations.

Proceedings of the Symposium on Theory of Computing, 2014

On the Power of Symmetric LP and SDP Relaxations.

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

A Parallel Repetition Theorem for Entangled Projection Games.

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

Direct Product Testing.

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

2013

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

Proceedings of the Innovations in Theoretical Computer Science, 2013

Approximate Constraint Satisfaction Requires Large LP Relaxations.

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Hypercontractivity, sum-of-squares proofs, and their applications.

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

Approximation Limits of Linear Programs (Beyond Hierarchies).

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Making the Long Code Shorter.

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Reductions between Expansion Problems.

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Making the long code shorter, with applications to the Unique Games Conjecture.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Subsampling Mathematical Relaxations and Average-case Complexity.

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

Finding Almost-Perfect Graph Bisections.

Proceedings of the Innovations in Computer Science, 2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Improved Algorithms for Unique Games via Divide and Conquer.

Electronic Colloquium on Computational Complexity (ECCC), 2010

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

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

Graph expansion and the unique games conjecture.

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

Fast SDP Algorithms for Constraint Satisfaction Problems.

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

Subexponential Algorithms for Unique Games and Related Problems.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Improved Rounding for Parallel Repeated Unique Games.

Proceedings of the Approximation, 2010

2009

Connections Between Unique Games and Multicut.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Subsampling Semidefinite Programs and Max-Cut on the Sphere.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Message passing algorithms and improved LP decoding.

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Towards computing the Grothendieck constant.

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

Towards a Study of Low-Complexity Graphs.

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

How to Round Any CSP.

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

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES.

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

2008

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

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

Asymptotically Optimal Hitting Sets Against Polynomials.

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

Rounding Parallel Repetitions of Unique Games.

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

2006

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

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

The Interval Liar Game.

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

An asymptotic approximation scheme for multigraph edge coloring.

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005