1 citations · 1 across the 3 of their papers we have counts for
5 papers · 1 filter
Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
Radu Curticapean, Holger Dell, Thore Husfeldt
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of -matchings can be det…
Counting Answers to Existential Questions
Holger Dell, Marc Roth, Philip Wellnitz
Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather tha…
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell +1
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-ti…
Note on "The Complexity of Counting Surjective Homomorphisms and Compactions"
Holger Dell
Focke, Goldberg, and Živný (arXiv 2017) prove a complexity dichotomy for the problem of counting surjective homomorphisms from a large input graph G without loops to a fixed graph…
Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Cornelius Brand, Holger Dell, Marc Roth
Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the rema…