Institute for Theoretical Computer Science

Department of Computer Science

ETH Zurich

8092 Zurich, CH

Office: 37.1 CAB

Homepage: `www.dsteurer.org`

Email: `dsteurer@inf.ethz.ch`

Born: February 16, 1984 — Heilbronn, Germany.

Nationality: German.

- Approximation algorithms and hardness of approximation, especially in the context of the Unique Games Conjecture.
- The power of mathematical programming relaxations, in particular semidefinite programming and the sum-of-squares method.
- Computational complexity of high-dimensional estimation problems that arise in machine learning, e.g., tensor decomposition.

Assistant Professor, Department of Computer Science, ETH Zurich.

**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.

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

**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.

**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.

*Conference committees:* APPROX 2018, 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, SODA, ITCS, ICALP, CCC, RANDOM, APPROX.

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

**ICERM**, workshop *semidefinite programming and graph algorithms*, Providence, February 2014.

**Simons Institute**, workshop *graph partitioning, semidefinite programming hierarchies, and the Unique Games Conjecture*, Berkeley, Fall 2014.

**Les Houches**, workshop *Optimization and Statistical Learning*, April 2017.

**Banff International Research Station (BIRS)**, workshop *computational complexity theory*, September 2016.

**Banff International Research Station (BIRS)**, workshop *Algebraic and spectral graph theory*, August 2016.

**Quarterly Theory Workshop**, *sum-of-squares and extension complexity*, Northwestern University, May 2016.

**Simons Institute**, workshop on *random instances and phase transitions*, May 2016.

**Schloss Dagstuhl**, seminar *constraint satisfaction problems*, July 2015.

**Simons Collaboration**, annual conference, New York, May 2015.

**Schloss Dagstuhl**, seminar *limitations of convex programming*, February 2015.

**Simons Symposium**, workshop *New Approaches in Approximation Algorithms*, San Juan, February 2015.

**Israel Institute for Advanced Studies**, *Midrasha Mathematicae*, Jerusalem, January 2015.

**Midwest Theory Day**, Ann Arbor, December 2014.

**Schloss Dagstuhl**, seminar *Optimal Algorithms and Proofs*, October 2014.

**Simons Institute**, workshop *Semidefinite Optimization, Approximation, and Applications*, September 2014.

**Cargese Workshop on Combinatorial Optimization**, distinguished speaker, September 2014.

**Simons Institute**, boot camp lectures for “Algorithmic Spectral Graph Theory” program, September 2014.

**Banff International Research Station (BIRS)**, workshop *Approximation algorithms and the hardness of approximation*, plenary talk, August 2014.

**Max Planck Institute for Computer Science**, distinguished speakers series, July 2014.

**SIAM Conf. on Discrete Math.**, minisymposium *Hardness of Approximation*, June 2014.

**Center for Computational Intractability**, workshop, Princeton, May 2014.

**Georgia Tech ARC Theory Day**, Atlanta, April 2014.

**TCS+**, online seminar series, December 2013.

**New York Theory Day**, November 2013.

**Simons Institute**, workshop *Real Analysis in Testing, Learning and Inapprox.*, Berkeley, August 2013.

**Schloss Dagstuhl**, seminar *Exponential Algorithms*, August 2013.

**Isaac Newton Institute (INI)**, program *Polynomial Optimisation* (two talks), Cambridge, July 2013.

**Banff Int’l Research Station (BIRS)**, workshop *Computational Complexity*, July 2013.

**École Polytechnique Fédérale de Lausanne (EPFL)**, tutorial on *extended formulations*, June 2013.

**Simons Symposium**, workshop *New Approaches in Approximation Algorithms*, U.S. Virgin Islands, January 2013.

**Mathematisches Forschungsinstitut Oberwolfach**, plenary talk at workshop *Computational Complexity*, November 2012.

**Summer school on semidefinite optimization**, organized by the research training group *Experimental and constructive algebra* at RWTH Aachen, funded by the German Research Foundation, September 2012.

**SIAM Conf. on Discrete Mathematics**, minisymposium *Approximation Algorithms*, June 2012.

**École Polytechnique Fédérale de Lausanne (EPFL)**, workshop Algorithmic Frontiers*, Lausanne, June 2012.

**STOC**, workshop *Unique Games Conjecture and Related Advances* (w. Raghavendra), May 2012.

**Banff International Research Station (BIRS)**, workshop *Approximation algorithms and the hardness of approximation*, December 2011.

**Mathematisches Forschungsinstitut Oberwolfach**, workshop Combinatorial Optimization*, November 2011.

**Fields Institute**, workshop *Approximability of CSPs*, Toronto, August 2011.

**Centrum Wiskunde & Informatica (CWI)**, *3rd SDP days: Applications of semidefinite programming*, Amsterdam, July 2011.

**Center for Computational Intractability**, workshop *Approximation Algorithms: The Last Decade and the Next*, Princeton, June 2011.

**Microsoft Research Redmond**, *Theory Day*, March 2011.

**Institut Henri Poincaré**, workshop *Metric embeddings, algorithms, and hardness of approximation*, Paris, January 2011.

**Microsoft Research India**, *School on Approximability*, Bangalore, January 2011.

**Center for Computational Intractability**, workshop *Barriers in Computational Complexity II*, Princeton, August 2010.

**Banff Int’l Research Station (BIRS)**, workshop *Computational Complexity*, August 2010.

**INFORMS**, session *Recent Applications of SDP*, San Diego, October 2009.

**China Theory Week**, Beijing, September 2009.

**Toyota Technological Institute (TTI)**, workshop *Approximation Algorithms and their Limitations*, Chicago, February 2009.

**9th Combinatorial Optimization Workshop**, Aussois, March 2005.

**MIT**, Stochastics and Statistics Seminar, April 2017.

**Princeton University**, PACM colloquium, March 2017.

**Princeton University**, theory seminar, March 2017.

**Institute for Advanced Study**, Math member seminar, March 2017.

**IST Austria**, colloquium, January 2017.

**ETH**, Mittagsseminar, January 2017.

**Princeton**, optimization seminar, November 2016.

**Institute for Advanced Study**, CSDM seminar, October 2016.

**EPFL**, theory seminar, July 2016.

**University of Pennsylvania**, theory lunch, March 2016.

**Institute for Advanced Study**, CSDM seminar, November 2015.

**MIT**, ToC colloquium, May 2015.

**EPFL**, theoretical computer science seminar, December 2014.

**KTH Stockholm**, theory seminar, April 2014.

**Cornell University**, theory seminar, December 2013.

**EPFL**, theory and combinatorics seminar, May 2013.

**Cornell University**, brown bag lunch, September 2012.

**Georgia Institute of Technology**, theory seminar, May 2012.

**Princeton University**, theory seminar, April 2012.

**Cornell University**, CS colloquium, summer 2011.

**UC Berkeley**, theory seminar & theory lunch, summer 2011.

**Harvard University**, CS colloquium, summer 2011.

**Weizmann Institute**, lecture series in cryptography and complexity, December 2010.

**Microsoft Research New England**, complexity reading group, August 2010.

**Georgia Institute of Technology**, ARC colloquium, November 2010.

**Harvard University**, TOC colloquium, October 2010.

**MIT**, ToC Colloquium, May 2010.

**Microsoft Research New England**, complexity reading group, May 2010.

**Princeton University**, theory lunch, April 2010.

**Center for Computational Intractability**, meeting, Princeton, March 2010.

**Carnegie Mellon University**, theory seminar, March 2010.

**IBM Research T.J. Watson**, theory seminar, March 2010.

**Institute for Advanced Study**, CSDM seminar, March 2010.

**UC Berkeley**, theory reading group, March 2010.

**New York University**, CS theory seminar, February 2010.

**Microsoft Research New England**, colloquium, February 2010.

**DIMACS & Rutgers**, theory seminar, March 2009.

**Princeton University**, theory lunch, March 2009.

**Microsoft Research New England**, colloquium, November 2008.

**Université Paris Sud**, Laboratoire de Recherche en Informatique, (LRI), algo seminar, Dec. 2008.

**Institute for Advanced Study**, CSDM seminar, Princeton, November 2008.

**Max Planck Institute for Computer Science**, Mittagsseminar, November 2004.

COLT 2017, COLT 2015, STOC 2015 (twice), CCC 2014 (twice), STOC 2014 (twice), ITCS 2013, FOCS 2011, FOCS 2010, RANDOM 2010, STOC 2010, SODA 2010, FOCS 2009 (twice), ICALP 2009, STOC 2009, SODA 2009, STOC 2008, SPAA 2006, SODA 2005.

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**), 2017S. 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**), 2017T. 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*.)