Dominik Scheder

According to our database, Dominik Scheder authored at least 42 papers between 2007 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

PPSZ for General k-SAT and CSP - Making Hertli's Analysis Simpler and 3-SAT Faster.

Dominik Scheder, John P. Steinberger

Comput. Complex., December, 2024

2021

PPSZ is better than you think.

Dominik Scheder

Electron. Colloquium Comput. Complex., 2021

Impatient PPSZ - A Faster Algorithm for CSP.

Shibo Li, Dominik Scheder

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

2020

Super Strong ETH is true for strong PPSZ.

Dominik Scheder, Navid Talebanfard

Electron. Colloquium Comput. Complex., 2020

Super Strong ETH Is True for PPSZ with Small Resolution Width.

Dominik Scheder, Navid Talebanfard

Proceedings of the 35th Computational Complexity Conference, 2020

2019

PPSZ for <i>k</i> ≥ 5: More Is Better.

Dominik Scheder

ACM Trans. Comput. Theory, 2019

Searching for Cryptogenography Upper Bounds via Sum of Square Programming.

Dominik Scheder, Shuyang Tang, Jiaheng Zhang

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

2018

PPSZ on CSP Instances with Multiple Solutions.

Dominik Scheder

Electron. Colloquium Comput. Complex., 2018

PPSZ for k ≥ 5: More Is Better.

Dominik Scheder

Electron. Colloquium Comput. Complex., 2018

Recent studies of agent incentives in internet resource allocation and pricing.

Yukun Cheng, Xiaotie Deng, Dominik Scheder

4OR, 2018

2017

Tighter Hard Instances for PPSZ.

Pavel Pudlák, Dominik Scheder, Navid Talebanfard

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster.

Dominik Scheder, John P. Steinberger

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Exponential Lower Bounds for <i>k</i>-SAT Algorithms.

Dominik Scheder

Encyclopedia of Algorithms, 2016

Derandomization of \(\boldsymbol{k}\) -SAT Algorithm.

Dominik Scheder

Encyclopedia of Algorithms, 2016

The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors.

Timon Hertli, Isabelle Hurbain, Sebastian Millius, Robin A. Moser, Dominik Scheder, May Szedlák

Proceedings of the Principles and Practice of Constraint Programming, 2016

2014

Cryptogenography.

Joshua Brody, Sune K. Jakobsen, Dominik Scheder, Peter Winkler

Proceedings of the Innovations in Theoretical Computer Science, 2014

Overlays and Limited Memory Communication.

Periklis A. Papakonstantinou, Dominik Scheder, Hao Song

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

2013

A new bound for 3-satisfiable MaxSat and its algorithmic application.

Gregory Z. Gutin, Mark Jones, Dominik Scheder, Anders Yeo

Inf. Comput., 2013

Overlays and Limited Memory Communication Mode(l)s.

Periklis A. Papakonstantinou, Dominik Scheder, Hao Song

Electron. Colloquium Comput. Complex., 2013

Inside the Simons Institute.

Dominik Scheder

Bull. EATCS, 2013

Exponential Lower Bounds for the PPSZ <i>k</i>-SAT Algorithm.

Dominik Scheder, Bangsheng Tang, Shiteng Chen, Navid Talebanfard

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Unsatisfiable CNF Formulas contain Many Conflicts.

Dominik Scheder

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas.

Dominik Scheder

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

On the Average Sensitivity and Density of k-CNF Formulas.

Dominik Scheder, Li-Yang Tan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2011

Algorithms and Extremal Properties of SAT and CSP.

Dominik Scheder

PhD thesis, 2011

A full derandomization of schöning's k-SAT algorithm.

Robin A. Moser, Dominik Scheder

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Improving PPSZ for 3-SAT using Critical Variables.

Timon Hertli, Robin A. Moser, Dominik Scheder

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

PPZ For More Than Two Truth Values - An Algorithm for Constraint Satisfaction Problems

Dominik Scheder

CoRR, 2010

Improving PPSZ for 3-SAT using Crtitical Variables

Timon Hertli, Robin A. Moser, Dominik Scheder

CoRR, 2010

A Full Derandomization of Schoening's k-SAT Algorithm

Robin A. Moser, Dominik Scheder

CoRR, 2010

Using CSP To Improve Deterministic 3-SAT

Konstantin Kutzkov, Dominik Scheder

CoRR, 2010

Using a Skewed Hamming Distance to Speed Up Deterministic Local Search

Dominik Scheder

CoRR, 2010

Unsatisfiable Linear CNF Formulas Are Large and Complex.

Dominik Scheder

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Unsatisfiable Linear CNF Formulas Are Large, and Difficult to Construct Explicitely

Dominik Scheder

CoRR, 2009

The Lovász Local Lemma and Satisfiability.

Heidi Gebauer, Robin A. Moser, Dominik Scheder, Emo Welzl

Proceedings of the Efficient Algorithms, 2009

2008

Satisfiability of Almost Disjoint CNF Formulas

Dominik Scheder

CoRR, 2008

An Improved Bound on the Number of Conflicts in Unsatisfiable k-CNF Formulas

Dominik Scheder, Philipp Zumstein

CoRR, 2008

How Many Conflicts Does It Need to Be Unsatisfiable?

Dominik Scheder, Philipp Zumstein

Proceedings of the Theory and Applications of Satisfiability Testing, 2008

Guided Search and a Faster Deterministic Algorithm for 3-SAT.

Dominik Scheder

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Partial Satisfaction of k-Satisfiable Formulas.

Claudia Käppeli, Dominik Scheder

Electron. Notes Discret. Math., 2007

Unsatisfiable Linear k-CNFs Exist, for every k

Dominik Scheder

CoRR, 2007

Satisfiability with Exponential Families.

Dominik Scheder, Philipp Zumstein

Proceedings of the Theory and Applications of Satisfiability Testing, 2007