VLDB 2026 Research / reviewers in the wild / expert
Timon Hertli
dblp:87/8575
· DBLP profile ↗
5ranked-venue papers
5as first author
0since 2021 · last 2016
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 4 · 4 first-authorArtificial intelligence and machine learning · 1 · 1 first-authorSoftware engineering, systems software and programming languages · 1 · 1 first-author
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
3 papers |
Automated reasoning and model checking · 52% Algorithms and data structures · 37% Computational complexity · 11% |
Topics — the 7 heaviest of 7, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Automated reasoning and model checking
satisfiability |
0.4 | 2 | 2014 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · SIAM J. Comput. 2014 Breaking the PPSZ Barrier for Unique 3-SAT · ICALP (1) 2014 |
Algorithms and data structures
exact exponential algorithms |
0.4 | 3 | 2014 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · SIAM J. Comput. 2014 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · FOCS 2011 Breaking the PPSZ Barrier for Unique 3-SAT · ICALP (1) 2014 |
Automated reasoning and model checking › satisfiability
k-SAT |
0.3 | 2 | 2014 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · SIAM J. Comput. 2014 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · FOCS 2011 |
Automated reasoning and model checking › satisfiability › k-SAT
3-SAT |
0.2 | 1 | 2014 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · SIAM J. Comput. 2014 |
Computational complexity › constraint satisfaction › SAT
Unique 3-SAT |
0.2 | 1 | 2014 | Breaking the PPSZ Barrier for Unique 3-SAT · ICALP (1) 2014 |
Algorithms and data structures › exact exponential algorithms
PPSZ algorithm |
0.1 | 1 | 2011 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · FOCS 2011 |
Algorithms and data structures › exact algorithms
satisfiability algorithms |
0.1 | 1 | 2011 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General · FOCS 2011 |
Methods — techniques the papers use, named apart from their topics
PPSZ algorithm · 0.4probabilistic analysis · 0.1cost function analysis · 0.1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 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 |
CP | 1 |
| 2014 | Breaking the PPSZ Barrier for Unique 3-SAT
Timon Hertli |
ICALP (1) | 1 |
| 2014 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in GeneralabstractThe PPSZ algorithm by Paturi, Pudlák, Saks, and Zane [J. ACM, 52 (2005), pp. 337--364] is the fastest known algorithm for Unique $k$-SAT, where the input formula does not have more than one satisfying assignment. For $k\geq 5$ the same bounds hold for general $k$-SAT. We show that this is also the case for k=3,4, using a slightly modified PPSZ algorithm. We do the analysis by defining a cost for satisfiable conjunctive normal form formulas, which we prove to decrease in each PPSZ step by a certain amount. This improves our previous best bounds with Moser and Scheder [Proceedings of STACS, 2011, pp. 237--248] for 3-SAT to $O(1.308^n)$ and for 4-SAT to $O(1.469^n)$. Furthermore, our analysis is much simpler than the existing analysis of PPSZ for general $k$-SAT. Timon Hertli |
SIAM J. Comput. | 1 |
| 2011 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in GeneralabstractThe PPSZ algorithm by Paturi, Pudlák, Saks, and Zane [1998] is the fastest known algorithm for Unique k-SAT, where the input formula does not have more than one satisfying assignment. For k≥5 the same bounds hold for general k-SAT. We show that this is also the case for k=3,4, using a slightly modified PPSZ algorithm. We do the analysis by defining a cost for satisfiable CNF formulas, which we prove to decrease in each PPSZ step by a certain amount. This improves our previous best bounds with Moser and Scheder [2011] for 3-SAT to O(1.308") and for 4-SAT to O(1.469"). Timon Hertli |
FOCS | 1 |
| 2011 | Improving PPSZ for 3-SAT using Critical Variables
Timon Hertli, Robin A. Moser, Dominik Scheder |
STACS | 1 |