Demo Data from VLDB 2026 / reviewers in the wild / expert
Andrew Kaploun
dblp:324/0584
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2022
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Artificial intelligence and machine learning · 1 · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 since 2021
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
1 paper |
Computational complexity · 54% Automated reasoning and model checking · 23% Algorithms and data structures · 23% |
Topics — the 5 heaviest of 5, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity › parameterized complexity
backdoor sets |
0.6 | 1 | 2022 | Faster Algorithms for Weak Backdoors · AAAI 2022 |
Computational complexity
parameterized complexity |
0.6 | 1 | 2022 | Faster Algorithms for Weak Backdoors · AAAI 2022 |
Algorithms and data structures › exact algorithms
SAT algorithms |
0.6 | 1 | 2022 | Faster Algorithms for Weak Backdoors · AAAI 2022 |
Automated reasoning and model checking
satisfiability |
0.6 | 1 | 2022 | Faster Algorithms for Weak Backdoors · AAAI 2022 |
Computational complexity › parameterized complexity
fixed-parameter tractability |
0.2 | 1 | 2022 | Faster Algorithms for Weak Backdoors · AAAI 2022 |
Methods — techniques the papers use, named apart from their topics
reduction · 0.6local search · 0.6branching algorithm · 0.6
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2022 | Faster Algorithms for Weak BackdoorsabstractA weak backdoor, or simply a backdoor, for a Boolean SAT formula F into a class of SAT formulae C is a partial truth assignment T such that F[T] is in C and satisfiability is preserved. The problem of finding a backdoor from class C1 into class C2, or WB(C1,C2), can be stated as follows: Given a formula F in C1, and a natural number k, determine whether there exists a backdoor for F into C2 assigning at most k variables. The class 0-Val contains all Boolean formulae with at least one negative literal in each clause. We design a new algorithm for WB(3CNF, 0-Val) by reducing it to a local search variant of 3-SAT. We show that our algorithm runs in time O*(2.562^k), improving on the previous state-of-the-art of O*(2.85^k). Here, the O* notation is a variant of the big-O notation that allows to omit polynomial factors in the input size. Next, we look at WB(3CNF, Null), where Null is the class consisting of the empty formula. This problem was known to have a trivial running time upper bound of O*(6^k) and can easily be solved in O*(3^k) time. We use a reduction to Conflict-Free-d-Hitting-Set to prove an upper bound of O*(2.2738^k), and also prove a lower bound of 2^o(k) assuming the Exponential Time Hypothesis. Finally, Horn is the class of formulae with at most one positive literal per clause. We improve the previous O*(4.54^k) running time for WB(3CNF, Horn) problem to O*(4.17^k), by exploiting the structure of the SAT instance to give a novel proof of the non-existence of the slowest cases after a slight restructuring of the branching priorities. Serge Gaspers, Andrew Kaploun |
AAAI | 2 |