Holger Dell

SODA Conference 2025 Conference Paper

Solving Polynomial Equations Over Finite Fields

• Holger Dell
• Anselm Haak
• Melvin Kallmayer
• Leo Wennmann

SODA Conference 2020 Conference Paper

Approximately counting and sampling small witnesses using a colourful decision oracle

• Holger Dell
• John Lapinskas
• Kitty Meeks

In this paper, we prove “black box” results for turning algorithms which decide whether or not a witness exists into algorithms to approximately count the number of witnesses, or to sample from the set of witnesses approximately uniformly, with essentially the same running time. We do so by extending the framework of Dell and Lapinskas (STOC 2018), which covers decision problems that can be expressed as edge detection in bipartite graphs given limited oracle access; our framework covers problems which can be expressed as edge detection in arbitrary k -hypergraphs given limited oracle access. (Simulating this oracle generally corresponds to invoking a decision algorithm.) This includes many key problems in both the fine-grained setting (such as k -SUM, k -OV and weighted k -Clique) and the parameterised setting (such as induced subgraphs of size k or weight- k solutions to CSPs). From an algorithmic standpoint, our results will make the development of new approximate counting algorithms substantially easier; indeed, it already yields a new state-of-the-art algorithm for approximately counting graph motifs, improving on Jerrum and Meeks (JCSS 2015) unless the input graph is very dense and the desired motif very small. Our k -hypergraph reduction framework generalises and strengthens results in the graph oracle literature due to Beame et al. (ITCS 2018) and Bhattacharya et al. (CoRR abs/1808. 00691).

STOC Conference 2018 Conference Paper

Extensor-coding

• Cornelius Brand
• Holger Dell
• Thore Husfeldt

STOC Conference 2018 Conference Paper

Fine-grained reductions from approximate counting to decision

• Holger Dell
• John Lapinskas

In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the polynomial-time setting, and a similar result of Müller (IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). While all these problems have simple algorithms over which it is conjectured that no polynomial improvement is possible, our reductions would remain interesting even if these conjectures were proved; they have only polylogarithmic overhead, and can therefore be applied to subpolynomial improvements such as the n 3 /exp(Θ(√log n ))-time algorithm for the Negative-Weight Triangle problem due to Williams (STOC 2014). Our framework is also general enough to apply to versions of the problems for which more efficient algorithms are known. For example, the Orthogonal Vectors problem over GF( m ) d for constant m can be solved in time n ·poly( d ) by a result of Williams and Yu (SODA 2014); our result implies that we can approximately count the number of orthogonal pairs with essentially the same running time. We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some 1 0 as part of the input). A full version of this paper containing detailed proofs is available at https://arxiv.org/abs/1707.04609.

STOC Conference 2018 Conference Paper

More consequences of falsifying SETH and the orthogonal vectors conjecture

• Amir Abboud
• Karl Bringmann
• Holger Dell
• Jesper Nederlof

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-time algorithms. The OV-conjecture in moderate dimension states there is no ε>0 for which an O ( N 2−ε ) poly ( D ) time algorithm can decide whether there is a pair of orthogonal vectors in a given set of size N that contains D -dimensional binary vectors. We strengthen the evidence for these hardness assumptions. In particular, we show that if the OV-conjecture fails, then two problems for which we are far from obtaining even tiny improvements over exhaustive search would have surprisingly fast algorithms. If the OV conjecture is false, then there is a fixed ε>0 such that: - For all d and all large enough k , there is a randomized algorithm that takes O ( n (1−ε) k ) time to solve the Zero-Weight- k -Clique and Min-Weight- k -Clique problems on d -hypergraphs with n vertices. As a consequence, the OV-conjecture is implied by the Weighted Clique conjecture. - For all c , the satisfiability of sparse TC1 circuits on n inputs (that is, circuits with cn wires, depth c log n , and negation, AND, OR, and threshold gates) can be computed in time O ((2−ε) n ).

STOC Conference 2017 Conference Paper

Homomorphisms are a good basis for counting small subgraphs

• Radu Curticapean
• Holger Dell
• Dániel Marx

SODA Conference 2012 Conference Paper

Kernelization of packing problems

• Holger Dell
• Dániel Marx

Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d -S et M atching for integers d ≥ 3 is the problem of finding a matching of size at least k in a given d -uniform hypergraph and has kernels with O ( k d ) edges. Recently, Bodlaender et al. [ICALP 2008], Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010] developed a framework for proving lower bounds on the kernel size for certain problems, under the complexity-theoretic hypothesis that coNP is not contained in NP/poly. Under the same hypothesis, we show lower bounds for the kernelization of d -S et M atching and other packing problems. Our bounds are tight for d -S et M atching: It does not have kernels with O ( k d−∊ ) edges for any ∊ > 0 unless the hypothesis fails. By reduction, this transfers to a bound of O ( k d − 1 − ∊ ) for the problem of finding k vertex-disjoint cliques of size d in standard graphs. It is natural to ask for tight bounds on the kernel sizes of such graph packing problems. We make first progress in that direction by showing non-trivial kernels with O ( k 2. 5 ) edges for the problem of finding k vertex-disjoint paths of three edges each. This does not quite match the best lower bound of O ( k 2−∊ ) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O ( k d −∊ ) for a problem in d -uniform hypergraphs, one should reduce from a carefully chosen d -partite problem that is still NP-hard. As an illustration, we apply this scheme to the vertex cover problem, which allows us to replace the number-theoretical construction by Dell and Van Melkebeek [STOC 2010] with shorter elementary arguments.

STOC Conference 2010 Conference Paper

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

• Holger Dell
• Dieter van Melkebeek

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d ≥ 3 and positive real ε we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n d-ε ) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems. For the vertex cover problem on n-vertex d-uniform hypergraphs, the above statement holds for any integer d ≥ 2. The case d=2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k 2-ε ) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.