algorithms for Boolean satisfiability; complexity theory; communication complexity

2005-2011: PhD, ETH Zurich
2003-2005: MSc, University of Colorado at Boulder, USA
1999-2003: undergraduate studies, Universität Erlangen-Nürnberg, Germany

09/2014-present: assistant professor, Shanghai Jiaotong University
spring 2014: postdoctoral researcher, IIIS, Tsinghua University, Beijing, China
fall 2013: postdoctoral fellow, Simons Institute, Berkeley, USA
2011-2013: postdoctoral researcher, Aarhus University, Aarhus, Denmark

algorithms for Boolean satisfiability; complexity theory; communication complexity

spring 2017: mathematical foundations of computer science
spring 2017: discrete mathematics; a massive open online course at coursera
fall 2016: algorithms and complexity
fall 2016: algorithm design and analysis
fall 2015: algorithms and complexity
fall 2015: algorithm design and analysis
spring 2014: discrete mathematics

Pavel Pudlák, Dominik Scheder, Navid Talebanfard, "Tighter Hard Instances for PPSZ", ICALP 2017 (to appear).

Dominik Scheder and John Steinberger, "PPSZ for General k-SAT — Making Hertli’s Analysis Simpler and 3-SAT Faster", CCC 2017 (to appear).

Timon Hertli, Isabelle Hurbain, Sebastian Millius, Robin A. Moser, Dominik Scheder, May Szedlák, “The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors”, CP 2016.

Dominik Scheder, “Derandomization of k-SAT Algorithm”, Encyclopedia of Algorithms 2016.

Dominik Scheder, "Exponential Lower Bounds for k-SAT Algorithms", Encyclopedia of Algorithms 2016.

Periklis Papakonstantinou, Dominik Scheder and Hao Song, “Overlays and Limited Memory Communication”, CCC 2014.

Joshua Brody, Sune Jakobsen, Dominik Scheder, and Peter Winkler, “Cryptogenography”, ITCS 2014.

Dominik Scheder, “Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas”, ISAAC 2013.

Dominik Scheder, “Unsatisfiable CNF Formulas Contain Many Conflicts”, ISAAC 2013.

Dominik Scheder and Li-Yang Tan, “On the average sensitivity and density of k-CNF formulas”, RANDOM 2013.

Shiteng Chen, Dominik Scheder, Navid Talebanfard, and Bangsheng Tang, “Exponential Lower Bounds for the PPSZ k-SAT Algorithm”, SODA 2013.

Gregory Gutin, Mark Jones, Dominik Scheder, and Anders Yeo, “A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application”, Information and Computation 2013.

Dominik Scheder, “Algorithms and Extremal Properties of SAT and CSP” (PhD Thesis), July 2011.

Robin A. Moser and Dominik Scheder, “A Full Derandomization of Schöning's k-SAT Algorithm”, STOC 2011.

Timon Hertli, Robin A. Moser, and Dominik Scheder, “Improving PPSZ for 3-SAT using Critical Variables”, STACS 2011.

Dominik Scheder, “Unsatisfiable Linear CNF Formulas are Large and Complex”, STACS 2010

Heidi Gebauer, Robin A. Moser, Dominik Scheder, Emo Welzl, “The Lovász Local Lemma and Satisfiability Efficient Algorithms”, 2009 (Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday).

Dominik Scheder, Philipp Zumstein, “How many Conflicts does it need to be Unsatisfiable”, SAT 2008.

Dominik Scheder, “Guided Search and a Faster Deterministic Algorithm for 3-SAT”, LATIN 2008.

Claudia Käppeli, Dominik Scheder, “Partial Satisfaction of k-Satisfiable Formulas”, EuroComb 2007.

Dominik Scheder, Philipp Zumstein, “Satisfiability with exponential families”, SAT 2007.

Dominik Scheder, “Approaches to Approximating the Minimum Weight k-Edge Connected Spanning Subgraph of a Mixed Graph”, Master's Thesis, University of Colorado at Boulder, 2005. Advisor: Harold N. Gabow.