Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Andrew Kaploun

dblp:324/0584 · DBLP profile ↗
← Back
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

TopicWeightPapersLastEvidence papers
Computational complexity › parameterized complexity
backdoor sets
0.612022
Faster Algorithms for Weak Backdoors · AAAI 2022
Computational complexity
parameterized complexity
0.612022
Faster Algorithms for Weak Backdoors · AAAI 2022
Algorithms and data structures › exact algorithms
SAT algorithms
0.612022
Faster Algorithms for Weak Backdoors · AAAI 2022
Automated reasoning and model checking
satisfiability
0.612022
Faster Algorithms for Weak Backdoors · AAAI 2022
Computational complexity › parameterized complexity
fixed-parameter tractability
0.212022
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
YearPublicationVenuePosition
2022 Faster Algorithms for Weak Backdoors
abstract
A 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
AAAI2