curriculum vitæ (pdf)

Personal

Born: February 16, 1984 — Heilbronn, Germany.

Nationality: German.

Research Interests

• Algorithm design through mathematical programming relaxations, in particular semidefinite programming and the sum-of-squares method.
• Computational complexity of high-dimensional estimation problems, e.g., tensor decomposition, clustering, Gaussian mixture models, and stochastic block models.
• Algorithmic aspects of robustness and differential privacy, especially for estimation.

Current Position

Associate Professor, Department of Computer Science, ETH Zurich.

Education

Ph.D. Computer Science, Princeton University, 2010. Advisor: Sanjeev Arora. Thesis: On the Complexity of Unique Games and Graph Expansion.

M.A. Computer Science, Princeton University, 2008.

B.Sc. & M.Sc. Computer Science, Saarland University, 2006.

Professional Experience

Associate Professor, Dept. of Comp. Sci., ETH Zurich, 2020–present.

Assistant Professor, Dept. of Comp. Sci., ETH Zurich, 2017–2020.

Visiting Assistant Professor, Institute for Advanced Study, Princeton, 2016–2017.

Assistant Professor, Dept. of Comp. Sci., Cornell University, 2012–2017.

Postdoctoral Researcher, Microsoft Research New England, 2010–2012.

Honors & Funding

ERC Consolidator Grant, 2019.

Michael and Sheila Held prize 2018 (with Raghavendra).

invited speaker at International Congress of Mathematicians 2018 (with Raghavendra).

Amnon Pazy Memorial Award, 2015 (with Dinur and Raghavendra).

STOC Best Paper Award, 2015, for Lower bounds on the size of semidefinite programming relaxations (w. Lee & Raghavendra).

Simons Collaboration: Algorithms and Geometry, 2014.

NSF Algorithmic Foundations Medium, Collaborative Research, 2014.

Microsoft Research Faculty Fellowship, 2014.

NSF CAREER Award, 2014.

Alfred P. Sloan Research Fellowship, 2014.

ACM Dissertation Award Honorable Mention, 2011.

FOCS Best Paper Award, 2010, for Subexponential Algorithms for Unique Games and Related Problems (w. Arora & Barak).

University Fellowship and Merit Award, Princeton University, 2006.

Günter Hotz Prize for best Master’s thesis in Computer Science, Saarland University, 2006.

Scholarship of the German National Merit Foundation, 2003–2006.

Bronze Medal, 15th International Olympiad in Informatics (IOI), USA, 2003.

Winner of the German national contest in computer science Bundeswettbewerb Informatik, 2002.

Service

Boards: internal member of Scientific Advisory Committee of Institute for Theoretical Studies at ETH Zurich (since September 2019).

Conference chair: APPROX 2018.

Conference committees: FOCS 2024, STOC 2023, ICALP 2023, COLT 2020 (senior pc), STOC 2019, COLT 2018, CCC 2016, FOCS 2014, STOC 2013, ICALP 2013, CATS 2013, APPROX 2012, SODA 2012.

Journal refereeing: Journal of the ACM, SIAM Journal of Computing, Theory of Computing.

Conference refereeing: STOC, FOCS, COLT, SODA, ITCS, ICALP, CCC, RANDOM, APPROX.

Grant refereeing: European Research Council (ERC), National Science Foundation (NSF), Natural Sciences and Engineering Research Council of Canada (NSERC).

Publications

H. Chen, J. Ding, T. d'Orsi, Y. Hua, C. Liu, D. Steurer: Private Graphon Estimation via Sum-of-Squares. In Proceedings of STOC 2024.

R. Buhai, D. Steurer: Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures. In Proceedings of COLT 2023.

Y. Hua, J. Ding, T. d'Orsi, D. Steurer: Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. In Proceedings of COLT 2023.

H. Chen, V. Cohen-Addad, T d'Orsi, A. Epasto, J. Imola, D. Steurer, S. Tiegel: Private estimation algorithms for stochastic block models and mixture models. In Proceedings of NeurIPS 2023. Spotlight

G. Novikov, D. Steurer, S. Tiegel: Robust Mean Estimation Without Moments for Symmetric Distributions. In Proceedings of NeurIPS 2023.

T. d’Orsi, R. Nasser, G. Novikov, D. Steurer: Higher degree sum-of-squares relaxations robust against oblivious outliers. In Proceedings of SODA 2023.

R. Buhai, P. K. Kothari, D. Steurer: Algorithms Approaching the Threshold for Semi-random Planted Clique. In Proceedings of STOC 2023.

J. Ding, T. d'Orsi, C. Liu, D. Steurer, S. Tiegel: Fast algorithm for overcomplete order-3 tensor decomposition. In Proceedings of COLT 2022.

T. d'Orsi, C. Liu, R. Nasser, G. Novikov, D.Steurer, S. Tiegel: Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers. In Proceedings of NeurIPS 2021.

J. Ding, T. d'Orsi, R. Nasser, D. Steurer: Robust Recovery for Stochastic Block Models. In Proceedings of FOCS 2021.

T. d'Orsi, G. Novikov, D. Steurer: Consistent regression when oblivious outliers overwhelm. In Proceedings of ICML 2021.

M. Bafna, B. Barak, P. K. Kothari, T. Schramm, D. Steurer: Playing Unique Games on Certified Small-Set Expanders. In Proceedings of STOC 2021.

D. Steurer, S. Tiegel: SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation. In Proceedings of SODA 2021.

T. d'Orsi, P. K. Kothari, G. Novikov, D. Steurer: Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. In Proceedings of FOCS 2020.

J. Ding, S. B. Hopkins, D. Steurer: Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks. In Proceedings of NeurIPS 2020. Spotlight

B. Barak, P. K. Kothari, D. Steurer: Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. In Proceedings of ITCS, January 2019.

P. Raghavendra, T. Schramm, D. Steurer: High-dimensional estimation from sum-of-squares proofs. In Proceedings of International Congress of Mathematicans (ICM), August 2018.

P. K. Kothari, J. Steinhard, D. Steurer. Improved clustering and robust moment estimation via sum-of-squares. In Proceedings of 50th Symposium on Theory of Computing (STOC), June 2018.

S. B. Hopkins, D. Steurer. Efficient Bayesian estimation from few samples: community detection and related problems. In Proceedings of 58th Symposium on Foundation of Computer Science (FOCS), 2017

S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, D. Steurer. The Power of Sum-of-Squares for Detecting Hidden Structures. In Proceedings of 58th Symposium on Foundation of Computer Science (FOCS), 2017

T. Schramm, D. Steurer. Fast and robust tensor decomposition with applications to dictionary learning. In Proceedings of Conference On Learning Theory (COLT), July 2017.

A. Potechin, D. Steurer. Exact tensor completion with sum-of-squares. In Proceedings of Conference On Learning Theory (COLT), July 2017.

B. Barak, P. K. Kothari, D. Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. In Proceedings of 49th Symposium on Theory of Computing (STOC), June 2017.

T. Ma, J. Shi, D. Steurer. Polynomial-time tensor decompositions with sum-of-squares. In Proceedings of 57th Symposium on Foundations of Computer Science (FOCS), October 2016.

S. B. Hopkins, T. Schramm, J. Shi, D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of 48th ACM Symposium on Theory of Computing (STOC), June 2016.

B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, J. Wright: Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM 2015.

S. B. Hopkins, J. Shi, D. Steurer. Tensor principal component analysis via sum-of-squares proofs. In Proceedings of Conference On Learning Theory (COLT), July 2015.

J. R. Lee, P. Raghavendra, D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of 47th ACM Symposium on Theory of Computing (STOC), June 2015. Best paper award.

B. Barak, J. Kelner, D. Steurer. Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. In Proceedings of 47th ACM Symposium on Theory of Computing (STOC), June 2015.

B. Barak, D. Steurer. Sum-of-Squares Proof and the Quest Toward Optimal Algorithms. In Proceedings of ICM, 2014.

B. Barak, J. Kelner, D. Steurer. Rounding Sum-of-Squares Relaxations. In Proceedings of 46th ACM Symposium on Theory of Computing (STOC), May 2014.

I. Dinur, D. Steurer. Analytical Approach to Parallel Repetition. In Proceedings of 46th ACM Symposium on Theory of Computing (STOC), May 2014.

I. Dinur, D. Steurer, T. Vidick. A Parallel Repetition Theorem for Entangled Projection Games. In Proceedings of IEEE Conference on Computational Complexity (CCC), June 2014.

I. Dinur, D. Steurer. Direct Product Testing. In Proceedings of IEEE Conference on Computational Complexity (CCC), June 2014.

J. R. Lee, P. Raghavendra, D. Steurer, N. Tan. Symmetric LP and SDP Relaxations. In Proceedings of IEEE Conference on Computational Complexity (CCC), June 2014.

S. O. Chan, J. R. Lee, P. Raghavendra, D. Steurer. Approximate Constraint Satisfaction Requires Large LP Relaxations. In Proceedings of 54th Symposium on Foundations of Computer Science (FOCS), October 2013. (Invited to special issue of SICOMP journal.)

B. Barak, G. Kindler, D. Steurer. On the Optimality of Semidefinite Relaxations for Average-Case and Generalized Constraint Satisfaction. In Proceedings of 4th Innovations in Theoretical Computer Science (ITCS), January 2013.

G. Braun, S. Fiorini, S. Pokutta, D. Steurer. Approximation Limits of Linear Programs (beyond Hierarchies). In Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS), October 2012.

B. Barak, P. Gopalan, J. Håstad, R. Meka, P. Raghavendra, D. Steurer. Making the Long Code Shorter. In Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS), October 2012. (Invited to special issue of SICOMP journal.)

S. Arora, C. Daskalakis, and D. Steurer. Message-Passing Algorithms and Improved LP Decoding. IEEE Transactions on Information Theory 58(12): 7260-7271 (2012).

B. Barak, F. Brandão, A. Harrow, J. Kelner, D. Steurer, Y. Zhou. Hypercontractivity, Sum-of-Squares Proofs, and their Applications. In Proceedings of 44th ACM Symposium on Theory of Computing (STOC), May 2012. (Invited to special issue of SICOMP journal.)

P. Raghavendra, D. Steurer, M. Tulsiani. Reductions between Expansion Problems. In Proceedings of IEEE Conference on Computational Complexity (CCC), June 2012.

B. Barak, P. Raghavendra, D. Steurer. Rounding SDP Hierarchies via Global Correlation. In Proceedings of 52nd Symposium on Foundations of Computer Science (FOCS), October 2011.

V. Guruswami, Y. Makarychev, P. Raghavendra, D. Steurer, Y. Zhou. Finding almost-perfect graph bisections. In Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), January 2011.

B. Barak, M. Hardt, T. Holenstein, and D. Steurer. Subsampling Mathematical Relaxations and Average-case Complexity. In Proceedings of 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2011.

S. Arora, B. Barak, D. Steurer. Subexponential Algorithms for Unique Games and Related Problems. In Proceedings of 51st Annual Symposium on Foundations of Computer Science (FOCS), October 2010. Best paper award.

D. Steurer. Improved Rounding for Parallel Repeated Unique Games. In Proceedings of 14th International Workshop on Randomization and Computation (RANDOM), September 2010.

P. Raghavendra and D. Steurer. Graph Expansion and the Unique Games Conjecture. In Proceedings of 42nd ACM Symposium on Theory of Computing (STOC), June 2010. (Invited to special issue of SICOMP journal.)

P. Raghavendra, D. Steurer, and P. Tetali. Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters. In Proceedings of 42nd ACM Symposium on Theory of Computing (STOC), June 2010.

D. Steurer. Fast SDP Algorithms for Constraint Satisfaction Problems. In Proceedings of 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2010.

P. Raghavendra, and D. Steurer. Integrality Gaps for Strong SDP Relaxations of Unique Games. In Proceedings of 50th Annual Symposium on Foundations of Computer Science (FOCS), October 2009.

P. Raghavendra, and D. Steurer. How to Round Any CSP. In Proceedings of 50th Annual Symposium on Foundations of Computer Science (FOCS), October 2009.

S. Arora, D. Steurer, and A. Wigderson. Towards a study of low-complexity graphs. In Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP), July 2009.

S. Arora, C. Daskalakis, and D. Steurer. Message-Passing Algorithms and Improved LP Decoding. In Proceedings of 41st ACM Symposium on Theory of Computing (STOC), May 2009.

P. Raghavendra and D. Steurer. Towards Computing the Grothendieck Constant. In Proceedings of 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2009.

B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer. Rounding Parallel Repetitions of Unique Games. In Proceedings of 49th Annual Symposium on Foundations of Computer Science (FOCS), October 2008.

M. Bläser, M. Hardt, and D. Steurer. Asymptotically Optimal Hitting Sets Against Polynomials. In Proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), July 2008.

S. Arora, S. A. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi. Unique Games on Expanding Constraint Graphs are Easy. In Proceedings of 40th ACM Symposium on Theory of Computing (STOC), May 2008. (Invited to Theory of Computing.)

P. Sanders and D. Steurer. An Asymptotic Approximation Scheme for Multigraph Edge Coloring. ACM Transactions on Algorithms 4(2): 1–24, May 2008. (Special Issue for invited papers of SODA 2005.)

B. Doerr, J. Lengler, and D. Steurer. The Interval Liar Game. In Proceedings of 17th International Symposium on Algorithms and Computation (ISAAC), December 2006.

D. Steurer. Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted Graphs. In Proceedings of 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), August 2006.

P. Sanders and D. Steurer. An Asymptotic Approximation Scheme for Multigraph Edge Coloring. In Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005. (Invited to special issue of ACM Transactions on Algorithms.)