back

Publications

Dominik Scheder
PPSZ is better than you think
to appear at the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)


Shibo Li and Dominik Scheder
Impatient PPSZ—a Faster algorithm for CSP
to appear at the 32nd International Symposium on Algo- rithms and Computation (ISAAC 2021)


Dominik Scheder, Navid Talebanfard
Super Strong ETH is true for strong PPSZ with small resolution width
35th Computational Complexity Conference (CCC 2020)


Dominik Scheder, Shuyang Tang, Jiaheng Zhang
Searching for Cryptogenography Upper Bounds via Sum of Square Programming
30th International Symposium on Algorithms and Computation (ISAAC 2019)


Dominik Scheder
PPSZ for k ≥ 5: More Is Better
ACM Transactions on Computation Theory (TOCT), 2019


Yukun Cheng, Xiaotie Deng, Dominik Scheder
Recent studies of agent incentives in internet resource allocation and pricing,
4OR, A Quarterly Journal of Operations Research


Pavel Pudlák, Dominik Scheder, Navid Talebanfard
Tighter Hard Instances for PPSZ
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).


Dominik Scheder and John Steinberger
PPSZ for General k-SAT — Making Hertli’s Analysis Simpler and 3-SAT Faster
Computational Complexity Conference 2017 (CCC 2017).


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 (full version)
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
The final version publication is available at link.springer.com


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
The final version publication is available at link.springer.com


Dominik Scheder
Guided Search and a Faster Deterministic Algorithm for 3-SAT
LATIN 2008
The final version publication is available at link.springer.com


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


Dominik Scheder, Philipp Zumstein
Satisfiability with exponential families
SAT 2007
The final version publication is available at link.springer.com


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