The Dominating \(H\)-Pattern problem generalizes the classical \(k\)-Dominating Set problem: for a fixed pattern \(H\) and a given graph \(G\), the goal is to find an induced subgraph \(S\) of \(G\) such that (1) \(S\) is isomorphic to \(H\), and (2) \(S\) forms a dominating set in \(G\). Fine-grained complexity results show that on worstcase inputs, any significant improvement over the naive brute-force algorithm is unlikely, as this would refute the Strong Exponential Time Hypothesis. Nevertheless, a recent work by Dransfeld et al. (ESA 2025) reveals some significant improvement potential particularly in sparse graphs.

To measure the similarity of the shape of point sets, rather than their mere closeness in space, various notions of a Hausdorff distance under translation have been investigated. Specifically, let P and Q denote point sets of n and m points, respectively, in ℝ^d. We consider the task of computing the minimum distance d(P,Q+τ) over an admissible set of translations τ ∈ T, where d(⋅, ⋅) denotes the Hausdorff distance under the L_∞-norm. As variants, we distinguish between continuous (T = ℝ^d) or discrete (T is a given finite set of t translations) as well as directed or undirected (choosing the directed or undirected Hausdorff distance for d(⋅, ⋅)). We seek to apply the paradigm of fine-grained complexity to understand the complexity of these variants, and in particular: How is the running time influenced by the dimension d, the relationship between n and m, and the specific choice of variant? As our main results, we obtain: - The asymmetric definition of the most studied variant, the continuous directed Hausdorff distance, results in an intrinsically asymmetric time complexity: While (Chan, SoCG'23) established a symmetric Õ((nm)^{d/2}) upper bound for all d ≥ 3 and proved it to be conditionally optimal for combinatorial algorithms whenever m ≤ n, we show that this lower bound does not hold for the case n ≪ m, by providing a combinatorial, almost-linear-time algorithm for d = 3 and n = m^{o(1)}. We further prove general, i.e., non-combinatorial, conditional lower bounds for d ≥ 3, in particular: (1) m^{⌊d/2⌋ - o(1)} for small n and (2) n^{d/2 - o(1)} for d = 3 and small m. - We observe that the directed and undirected case is closely related, in particular, all our lower bounds for d ≥ 3 hold for both the directed and undirected variant. A remarkable exception is the case of d = 1 for which we provide a conditional separation. Specifically, in contrast to the undirected variants being solvable in near-linear time (Rote, IPL'91), we show that the directed variants are at least as hard as the additive problem MaxConv LowerBound introduced in (Cygan, Mucha, Wegrzycki and Wlodarczyk, TALG'19). - We show that the discrete variants reduce to a variant of 3SUM for d ≤ 3. This gives a barrier in proving a tight lower bound of these variants under the Orthogonal Vectors Hypothesis (OVH); in contrast, the continuous variants admit a tight conditional lower bound under OVH in d = 2 (Bringmann, Nusser, JoCG'21). These results reveal an intricate interplay of dimensionality, symmetry and discreteness in determining the fine-grained complexity of computing Hausdorff distances under translation.

The Pareto sum of two-dimensional point sets P and Q in ℝ² is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets P and Q of size n suffers from conditional lower bounds that rule out strongly subquadratic O(n^{2-ε})-time algorithms, even when the output size is Θ(n). Naturally, we ask: How efficiently can we approximate Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is fine-grained equivalent to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable Õ(n^{1.5})-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.

Consider the fundamental task of finding independent sets of (constant) size k in a given n-node hypergraph. How much is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges m? Turán’s theorem implies that the problem is trivial if m = O(n^{2-ε}) for some ε > 0. Above that threshold (i.e., if m = Θ(n^γ) for some γ ≥ 2), we give a perhaps surprising algorithm with running time O(min{ n^({ω/3}k) + m^{k/3}, n^k}) (for k divisible by 3), which is essentially conditionally optimal for all γ ≥ 2, assuming the k-clique and 3-uniform hyperclique hypotheses (here, ω ≤ 2.372 denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity that is sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size k in sparse instances of Boolean constraint satisfaction problems, where n and m denote the number of variables and constraints, respectively. Our results include, among others: - an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and the binary Implication constraints, with a running time of Θ(m^{ω k/6 ± c}). - the identification of a large class of constraint families ℱ that exhibits a sharp phase transition: there is a threshold γ_ℱ such that the problem is trivial for m = O(n^{γ_ℱ-ε}), but requires essentially brute-force running time Θ(n^{k±c}) for m = Ω(n^{γ_ℱ}), assuming the 3-uniform hyperclique hypothesis. In general, we observe a rich landscape of time complexities. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone.

We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS'96, SICOMP'00) gave a surprising randomized algorithm to verify associativity of an operation odot: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S.

Abstract The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and its approximation performance is poor in the worst case. Englert, Röglin, and Vöcking (Algorithmica, 2014) provided a smoothed analysis in the so-called one-step model in order to explain the performance of 2-opt on d-dimensional Euclidean instances, both in terms of running-time and in terms of approximation ratio. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation $$\sigma $$ , yields only weak bounds. We prove bounds that are polynomial in n and $$1/\sigma $$ for the smoothed running-time with Gaussian perturbations. In addition, our analysis for Euclidean distances is much simpler than the existing smoothed analysis. Furthermore, we prove a smoothed approximation ratio of $$O(\log (1/\sigma ))$$ . This bound is almost tight, as we also provide a lower bound of $$\Omega (\frac{\log n}{\log \log n})$$ for $$\sigma = O(1/\sqrt{n})$$ . Our main technical novelty here is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and local optimum on all inputs (which only allows for a bound of $$O(1/\sigma )$$ ), but simultaneously bound them on the same input.

Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, ’78) and is EXPSPACE -hard already under unary encodings (Lipton, ’76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most \(n^{2^{\mathcal {O}(d \log (d))}}\) , where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d -dimensional unary VASS that are only witnessed by runs of length at least \(n^{2^{\Omega (d)}}\) . Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated \(\log (d)\) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic \(n^{2^{\mathcal {O}(d)}}\) -time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic \(n^{2^{o(d)}}\) -time algorithm, conditioned upon the exponential time hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in \(\mathcal {O}(n^{d+1})\) time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that \(n^{2-o(1)}\) time is required under the k -cycle hypothesis. In general, for any fixed dimension d ≥ 4, we show that \(n^{d-2-o(1)}\) time is required under the 3-uniform hyperclique hypothesis.

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphabets. We show that this barrier appears in many variations throughout the algorithmic literature by introducing a framework of Colored Walk problems. These yield fine-grained equivalent formulations of the NFA Acceptance problem as problems concerning detection of an $s$-$t$-walk with a prescribed color sequence in a given edge- or node-colored graph. For NFA Acceptance on sparse NFAs (or equivalently, Colored Walk in sparse graphs), a tight lower bound under the Strong Exponential Time Hypothesis has been rediscovered several times in recent years. We show that our hardness hypothesis, which concerns dense NFAs, has several interesting implications: - It gives a tight lower bound for Context-Free Language Reachability. This proves conditional optimality for the class of 2NPDA-complete problems, explaining the cubic bottleneck of interprocedural program analysis. - It gives a tight $(n+nm^{1/3})^{1-o(1)}$ lower bound for the Word Break problem on strings of length $n$ and dictionaries of total size $m$. - It implies the popular OMv hypothesis. Since the NFA acceptance problem is a static (i.e., non-dynamic) problem, this provides a static reason for the hardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve several interesting barriers. Conversely, a refutation of the NFA Acceptance hypothesis may lead the way to attacking the current barriers observed for Context-Free Language Reachability, the Word Break problem and the growing list of dynamic problems proven hard under the OMv hypothesis.

The study of domination in graphs has led to a variety of domination problems studied in the literature. Most of these follow the following general framework: Given a graph $G$ and an integer $k$, decide if there is a set $S$ of $k$ vertices such that (1) some inner property $ϕ(S)$ (e.g., connectedness) is satisfied, and (2) each vertex $v$ satisfies some domination property $ρ(S, v)$ (e.g., there is an $s\in S$ that is adjacent to $v$). Since many real-world graphs are sparse, we seek to determine the optimal running time of such problems in both the number $n$ of vertices and the number $m$ of edges in $G$. While the classic dominating set problem admits a rather limited improvement in sparse graphs (Fischer, Künnemann, Redzic SODA'24), we show that natural variants studied in the literature admit much larger speed-ups, with a diverse set of possible running times. Specifically, we obtain conditionally optimal algorithms for: 1) $r$-Multiple $k$-Dominating Set (each vertex must be adjacent to at least $r$ vertices in $S$): If $r\le k-2$, we obtain a running time of $(m/n)^{r} n^{k-r+o(1)}$ that is conditionally optimal assuming the 3-uniform hyperclique hypothesis. In sparse graphs, this fully interpolates between $n^{k-1\pm o(1)}$ and $n^{2\pm o(1)}$, depending on $r$. Curiously, when $r=k-1$, we obtain a randomized algorithm beating $(m/n)^{k-1} n^{1+o(1)}$ and we show that this algorithm is close to optimal under the $k$-clique hypothesis. 2) $H$-Dominating Set ($S$ must induce a pattern $H$). We conditionally settle the complexity of three such problems: (a) Dominating Clique ($H$ is a $k$-clique), (b) Maximal Independent Set of size $k$ ($H$ is an independent set on $k$ vertices), (c) Dominating Induced Matching ($H$ is a perfect matching on $k$ vertices).

What is the time complexity of matrix multiplication of sparse integer matrices with min nonzeros in the input and mout nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of min vs. mout, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication.

We revisit the classic k-Dominating Set problem. Besides its importance as perhaps the most natural W[2]-complete problem, it is among the first problems for which a tight nk-o(1) conditional lower bound (for all sufficiently large k), based on the Strong Exponential Time Hypothesis (SETH), was shown (Patrascu and Williams, SODA 2007). Notably, however, the underlying reduction creates dense graphs, raising the question: how much does the sparsity of the graph affect its fine-grained complexity?

Klee's measure problem (computing the volume of the union of $n$ axis-parallel boxes in $\mathbb{R}^d$) is well known to have $n^{\frac{d}{2}\pm o(1)}$-time algorithms (Overmars, Yap, SICOMP'91; Chan FOCS'13). Only recently, a conditional lower bound (without any restriction to ``combinatorial'' algorithms) could be shown for $d=3$ (Künnemann, FOCS'22). Can this result be extended to a tight lower bound for dimensions $d\ge 4$? In this paper, we formalize the technique of the tight lower bound for $d=3$ using a combinatorial object we call prefix covering design. We show that these designs, which are related in spirit to combinatorial designs, directly translate to conditional lower bounds for Klee's measure problem and various related problems. By devising good prefix covering designs, we give the following lower bounds for Klee's measure problem in $\mathbb{R}^d$, the depth problem for axis-parallel boxes in $\mathbb{R}^d$, the largest-volume/max-perimeter empty (anchored) box problem in $\mathbb{R}^{2d}$, and related problems: - $Ω(n^{1.90476})$ for $d=4$, - $Ω(n^{2.22222})$ for $d=5$, - $Ω(n^{d/3 + 2\sqrt{d}/9-o(\sqrt{d})})$ for general $d$, assuming the 3-uniform hyperclique hypothesis. For Klee's measure problem and the depth problem, these bounds improve previous lower bounds of $Ω(n^{1.777...}), Ω(n^{2.0833...})$ and $Ω(n^{d/3 + 1/3 + Θ(1/d)})$ respectively. Our improved prefix covering designs were obtained by (1) exploiting a computer-aided search using problem-specific insights as well as SAT solvers, and (2) showing how to transform combinatorial covering designs known in the literature to strong prefix covering designs. In contrast, we show that our lower bounds are close to best possible using this proof technique.

Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackoff's bounding technique to show that if coverability holds then there is a run of length at most $n^{2^{\mathcal{O}(d \log d)}}$, where $d$ is the dimension and $n$ is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in $d$-dimensional unary VASS that are only witnessed by runs of length at least $n^{2^{Ω(d)}}$. Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated $\log(d)$ factor, thus matching Lipton's lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic $n^{2^{\mathcal{O}(d)}}$-time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic $n^{2^{o(d)}}$-time algorithm, conditioned upon the Exponential Time Hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in $\mathcal{O}(n^{d+1})$-time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that $n^{2-o(1)}$-time is required under the $k$-cycle hypothesis. In general fixed dimension $d$, we show that $n^{d-2-o(1)}$-time is required under the 3-uniform hyperclique hypothesis.

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L₁ norm in ℝ^d, we provide an 𝒪(n^{2(d+1)})-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problem-specific insight leads to a (1+ε)-approximation in time 𝒪(n³/ε²). We then show how to obtain a subcubic 𝒪̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure. We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems.

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in $d$-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in $\widetilde{\mathcal{O}}(n^{5/3})$ time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time $\mathcal{O}(n^{2-δ})$ for some $δ>0$. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in $\mathbb{R}^3$ or congruent equilateral triangles in $\mathbb{R}^2$. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in $\mathbb{R}^2$. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in~$\mathbb{R}^{12}$, distinguishing between diameter 2 and 3 needs quadratic time (ruling out $(3/2-\varepsilon)$- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter $2$ and $3$ in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors.

We revisit the classic geometric problem of computing the volume of the union of n 3-dimensional axis-parallel boxes (Klee’s measure problem in $3 D$). It is well known that the problem can be solved in time $O\left(n^{3 / 2}\right)$ (Overmars, Yap SICOMP’91; Chan FOCS’13). Can we justify this 30-year old barrier of $n^{3 / 2 \pm o(1)}$ under plausible fine-grained complexity assumptions? The only previous conditional lower bound (Chan Comp. Geom.’10) shows that this barrier holds for purely combinatorial algorithms, i.e., algorithms avoiding algebraic techniques for fast matrix multiplication. This leaves open an algorithmic improvement exploiting algebraic techniques, and does not give any superlinear bound if the matrix multiplication exponent $\omega$ turns out to be equal to 2. We resolve this issue by giving a tight conditional lower bound for general algorithms, based on the 3-uniform hyperclique hypothesis. Specifically, we prove that an $O\left(n^{3 / 2-\epsilon}\right)$ algorithm for Klee’s measure problem in 3D would give a $O\left(n^{k-\epsilon^{\prime}}\right)$-time algorithm for counting k-cliques in 3-uniform hypergraphs - this in turn would give a novel $O\left(\left(2-\epsilon^{\prime \prime}\right)^{n}\right)$-algorithm for Max-3SAT. Our lower bound can be generalized to $n^{\frac{d}{3-3 / d}}-o(1)$, which matches the upper bound up to a factor of $n^{\frac{d-3}{6-6 / d}+o(1)}$ and separates the general problem from popular special cases: For all $d \geq 3$, known $\tilde{O}\left(n^{\frac{d+1}{3}}\right)$ algorithms (Bringmann Comp. Geom.’12; Chan FOCS’13) compute the problem for arbitrary hypercubes polynomially faster than our lower bound for the general problem.

An extensive research effort targets optimal (in)approximability results for various NP-hard optimization problems. Notably, the works of (Creignou'95) as well as (Khanna, Sudan, Trevisan, Williamson'00) establish a tight characterization of a large subclass of MaxSNP, namely Boolean MaxCSPs and further variants, in terms of their polynomial-time approximability. Can we obtain similarly encompassing characterizations for classes of polynomial-time optimization problems? To this end, we initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of k-XOR and Maximum k-Cover). Specifically, for each k, MaxSP_k denotes the class of O(m^k)-time problems of the form max_{x_1,… , x_k} #{y : ϕ(x_1,… ,x_k,y)} where ϕ is a quantifier-free first-order property and m denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and exact Max-3-SAT}, we show that for any MaxSP_k problem definable by a quantifier-free m-edge graph formula φ, the best possible approximation guarantee in faster-than-exhaustive-search time O(m^{k-δ})falls into one of four categories: - optimizable to exactness in time O(m^{k-δ}), - an (inefficient) approximation scheme, i.e., a (1+ε)-approximation in time O(m^{k-f(ε)}), - a (fixed) constant-factor approximation in time O(m^{k-δ}), or - a nm^ε-approximation in time O(m^{k-f(ε)}). We obtain an almost complete characterization of these regimes, for MaxSP_k as well as for an analogously defined minimization class MinSP_k. As our main technical contribution, we show how to rule out the existence of approximation schemes for a large class of problems admitting constant-factor approximations, under a hypothesis for exact Sparse Max-3-SAT algorithms posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we observe: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.

We revisit a classical problem in computational geometry: Determine the largest copy of a simple polygon P that can be placed into the simple polygon Q. Despite significant effort studying a number of settings, known algorithms require high polynomial running times, even for the interesting case when either P or Q have constant size. (Barequet and Har-Peled, 2001) give a conditional lower bound of n2–o(1) under the 3SUM conjecture when P and Q are (convex) polygons with Θ(n) vertices each. This leaves open whether we can establish (1) hardness beyond quadratic time and (2) any superlinear bound for constant-sized P or Q. In this paper, we affirmatively answer these questions under the higher-order kSUM conjecture, proving natural hardness results that increase with each degree of freedom (scaling, x-translation, y-translation, rotation): (scaling, x-translation:) Finding the largest copy of P that can be x-translated into Q requires time n2–o(1) under the 3SUM conjecture, even for orthogonal (rectilinear) polygons P, Q with O(1) and n vertices, respectively. (scaling, x-translation, y-translation:) Finding the largest copy of P that can be arbitrarily translatedinto Q requires time n2–o(1) under the 4SUM conjecture, even for orthogonal polygons P, Q with O(1) and n vertices, respectively. This establishes the same lower bound under the assumption that Subset Sum cannot be solved in time O((2–∊)n/2) for any ∊ > 0. The above lower bounds are almost tight when one of the polygons is of constant size: Using an offline dynamic algorithm for maintaining the area of a union of rectangles due to Overmars and Yap, we obtain an -time algorithm for orthogonal polygons P, Q with p and q vertices, respectively. This matches the lower bounds up to an n1/2+o(1)-factor when P, Q have O(1) and n vertices. (scaling, x-translation, y-translation, rotation:) Finally, finding the largest copy of P that can be arbitrarily rotated and translated into Q requires time n3–o(1) under the 5SUM conjecture. As in our reductions, each degree of freedom determines one summand in a kSUM instance, these lower bounds appear likely to be best possible under kSUM. We are not aware of any other such natural (degree of freedom + 1)-SUM hardness for a geometric optimization problem. Finally, we prove an additional tight OV hardness of the translations-only case.

We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the $k$-XOR problem. Specifically, we define MaxSP as the class of problems definable as $\max_{x_1,\dots,x_k} \#\{ (y_1,\dots,y_\ell) : ϕ(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $ϕ$ is a quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On $m$-sized structures, we can solve each such problem in time $O(m^{k+\ell-1})$. Our results are: - We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under *deterministic* fine-grained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of $O(m^{k+\ell-1})$ for *all* problems in MaxSP/MinSP by a polynomial factor. - This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic $c$-approximation would give a $(c+\varepsilon)$-approximation for all MaxSP/MinSP problems in time $O(m^{k+\ell-1-δ})$, where $\varepsilon > 0$ can be chosen arbitrarily small. Combining our completeness with~(Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is *equivalent* to giving a $O(1)$-approximation for all MinSP problems in faster-than-$O(m^{k+\ell-1})$ time.

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}). Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).

The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length n in the plane, the fastest known algorithm runs in time Õ( n 5 ) [12]. This is achieved by constructing an arrangement of disks of size Õ( n 4 ), and then traversing its faces while updating reachability in a directed grid graph of size N := Õ( n 5 ), which can be done in time Õ(√ N ) per update [27]. The contribution of this article is two-fold. First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than Õ(√ N ), we improve this part of the algorithm: We observe that an offline variant of dynamic s - t -reachability in directed grid graphs suffices, and we solve this variant in amortized time Õ( N 1/3 ) per update, resulting in an improved running time of Õ( N 4.66 ) for the discrete Fréchet distance under translation. Second, we provide evidence that constructing the arrangement of size Õ( N 4 ) is necessary in the worst case by proving a conditional lower bound of n 4 - o(1) on the running time for the discrete Fréchet distance under translation, assuming the Strong Exponential Time Hypothesis.

To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean constraint satisfaction with size constraint exactly $k$. More precisely, we aim to determine, for any finite constraint family, the optimal running time $f(k)n^{g(k)}$ required to find satisfying assignments that set precisely $k$ of the $n$ variables to $1$. Under central hardness assumptions on detecting cliques in graphs and 3-uniform hypergraphs, we give an almost tight characterization of $g(k)$ into four regimes: (1) Brute force is essentially best-possible, i.e., $g(k) = (1\pm o(1))k$, (2) the best algorithms are as fast as current $k$-clique algorithms, i.e., $g(k)=(ω/3\pm o(1))k$, (3) the exponent has sublinear dependence on $k$ with $g(k) \in [Ω(\sqrt[3]{k}), O(\sqrt{k})]$, or (4) the problem is fixed-parameter tractable, i.e., $g(k) = O(1)$. This yields a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a $f(k)n^{4\sqrt{k}}$-time algorithm for SubsetSum with precedence constraints parameterized by the target $k$ -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.

Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified whenever we aim to quantify the similarity of the curves' shapes rather than their positioning in the plane, e.g., to compare the similarity of handwritten characters. Perhaps the most natural such notion is the (discrete) Fréchet distance under translation. Unfortunately, the algorithmic literature on this problem yields a very pessimistic view: On polygonal curves with $n$ vertices, the fastest algorithm runs in time $O(n^{4.667})$ and cannot be improved below $n^{4-o(1)}$ unless the Strong Exponential Time Hypothesis fails. Can we still obtain an implementation that is efficient on realistic datasets? Spurred by the surprising performance of recent implementations for the Fréchet distance, we perform algorithm engineering for the Fréchet distance under translation. Our solution combines fast, but inexact tools from continuous optimization (specifically, branch-and-bound algorithms for global Lipschitz optimization) with exact, but expensive algorithms from computational geometry (specifically, problem-specific algorithms based on an arrangement construction). We combine these two ingredients to obtain an exact decision algorithm for the Fréchet distance under translation. For the related task of computing the distance value up to a desired precision, we engineer and compare different methods. On a benchmark set involving handwritten characters and route trajectories, our implementation answers a typical query for either task in the range of a few milliseconds up to a second on standard desktop hardware. We believe that our implementation will enable the use of the Fréchet distance under translation in applications, whereas previous approaches would have been computationally infeasible.

To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size N down to size n << N, it certainly makes it easier to store and transmit efficiently, but does it also make it easier to process? In this paper we consider lossless compression schemes, and ask if we can run our computations on the compressed data as efficiently as if the original data was that small. That is, if an operation has time complexity T(input-size), can we perform it on the compressed representation in time T(n) rather than T(N)? We consider the most basic linear algebra operations: inner product, matrix-vector multiplication, and matrix multiplication. In particular, given two compressed vectors, can we compute their inner product in time O(n)? Or perhaps we must decompress first and then multiply, spending Omega(N) time? The answer depends on the compression scheme. While for simple ones such as Run-Length-Encoding (RLE) the inner product can be done in O(n) time, we prove that this is impossible for compressions from a richer class: essentially n^2 or even larger runtimes are needed in the worst case (under complexity assumptions). This is the class of \emph{grammar-compressions} containing most popular methods such as the Lempel-Ziv family. These schemes are more compressing than the simple RLE, but alas, we prove that performing computations on them is much harder.

The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group 1) without revealing who was the origin of this information and 2) without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al. gave a 2-round protocol enabling the two players to succeed with probability 1/3 and showed the hardness result that no protocol can give a success probability of more than 3/8. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability of better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to 0.3384, that is, give a protocol leading to this success probability. Unfortunately, already our smallest protocol beating the previous 1/3 success probability takes up 16 rounds of communication. The protocol leading to the bound of 0.3384 even in a compact representation consists of 18248 game states. These numbers suggest that the task of finding good protocols for the cryptogenography problem as well as understanding their structure is harder than what the simple problem formulation suggests.

An important class of problems in logics and database theory is given by fixing a first-order property psi over a relational structure, and considering the model-checking problem for psi. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of fine-grained complexity in P, by showing that the (Sparse) Orthogonal Vectors problem is complete for this class under fine-grained reductions. This raises the question whether fine-grained complexity can yield a precise understanding of all first-order model-checking problems. Specifically, can we determine, for any fixed first-order property psi, the exponent of the optimal running time O(m^{c_psi}), where m denotes the number of tuples in the relational structure? Towards answering this question, in this work we give a dichotomy for the class of exists^k-forall-quantified graph properties. For every such property psi, we either give a polynomial-time improvement over the baseline O(m^k)-time algorithm or show that it requires time m^{k-o(1)} under the hypothesis that MAX-3-SAT has no O((2-epsilon)^n)-time algorithm. More precisely, we define a hardness parameter h = H(psi) such that psi can be decided in time O(m^{k-epsilon}) if h <=2 and requires time m^{k-o(1)} for h >= 3 unless the h-uniform HyperClique hypothesis fails. This unveils a natural hardness hierarchy within first-order properties: for any h >= 3, we show that there exists a exists^k-forall-quantified graph property psi with hardness H(psi)=h that is solvable in time O(m^{k-epsilon}) if and only if the h-uniform HyperClique hypothesis fails. Finally, we give more precise upper and lower bounds for an exemplary class of formulas with k=3 and extend our classification to a counting dichotomy.

The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in near-quadratic time, a strongly subquadratic algorithm cannot exist unless the Strong Exponential Time Hypothesis fails. Still, fast practical implementations of the Fréchet distance, in particular for realistic input curves, are highly desirable. This has even lead to a designated competition, the ACM SIGSPATIAL GIS Cup 2017: Here, the challenge was to implement a near-neighbor data structure under the Fréchet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fréchet distance. In this work, we present a fast, certifying implementation for deciding the Fréchet distance, in order to (1) complement its pessimistic worst-case hardness by an empirical analysis on realistic input data and to (2) improve the state of the art for the GIS Cup challenge. We experimentally evaluate our implementation on a large benchmark consisting of several data sets (including handwritten characters and GPS trajectories). Compared to the winning implementation of the GIS Cup, we obtain running time improvements of up to more than two orders of magnitude for the decision procedure and of up to a factor of 30 for queries to the near-neighbor data structure.

The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length n in the plane, the fastest known algorithm runs in time Õ(n5) [Ben Avraham, Kaplan, Sharir ′15]. This is achieved by constructing an arrangement of disks of size O(n4), and then traversing its faces while updating reachability in a directed grid graph of size N = O(n2), which can be done in time per update [Diks, Sankowski ′07]. The contribution of this paper is two-fold. First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than , we improve this part of the algorithm: We observe that an offline variant of dynamic s-t-reachability in directed grid graphs suffices, and we solve this variant in amortized time Õ(N1/3) per update, resulting in an improved running time of Õ(n4.66 …) for the discrete Fréchet distance under translation. Second, we provide evidence that constructing the arrangement of size O(n4) is necessary in the worst case, by proving a conditional lower bound of n4–o(1) on the running time for the discrete Fréchet distance under translation, assuming the Strong Exponential Time Hypothesis.

A fundamental problem on strings in the realm of approximate string matching is pattern matching with mismatches: Given a text t, a pattern p, and a number k, determine whether some substring of t has Hamming distance at most k to p; such a substring is called a k-match. As real-world texts often come in compressed form, we study the case of searching for a small pattern p in a text t that is compressed by a straight-line program. This grammar compression is popular in the string community, since it is mathematically elegant and unifies many practically relevant compression schemes such as the Lempel-Ziv family, dictionary methods, and others. We denote by m the length of p and by n the compressed size of t. While exact pattern matching, that is, the case k = 0, is known to be solvable in near-linear time Õ(n + m) [Jeż TALG’15], despite considerable interest in the string community, the fastest known algorithm for pattern matching with mismatches runs in time [Gawrychowski, Straszak ISAAC’13], which is far from linear even for very small k. In this paper, we obtain an algorithm for pattern matching with mismatches running in time Õ((n + m) poly(k)). This is near-linear in the input size for any constant (or slightly superconstant) k. We obtain analogous running time for counting and enumerating all k-matches. Our algorithm is based on a new structural insight for approximate pattern matching, essentially showing that either the number of k-matches is very small or both text and pattern must be almost periodic. While intuitive and simple for exact matches, such a characterization is surprising when allowing k mismatches.

Zwick’s (1+ε)-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time Õ(nω/ε logW), where ω ≤ 2.373 is the exponent of matrix multiplication and W denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound.

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called k-LCIS: Given k integer sequences $$X_1,\dots ,X_k$$ of length at most n, the task is to determine the length of the longest common subsequence of $$X_1,\dots ,X_k$$ that is also strictly increasing. Especially for the case of $$k=2$$ (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case. Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as Longest Common Subsequence. We further strengthen this lower bound (1) to rule out $${\mathcal {O}}\left( (nL)^{1-\varepsilon }\right) $$ time algorithms for LCIS, where L denotes the solution size, (2) to rule out $${\mathcal {O}}\left( n^{k-\varepsilon }\right) $$ time algorithms for k-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.

Motivated by studying the power of randomness, certifying algorithms and barriers for fine-grained reductions, we investigate the question whether the multiplication of two n x n matrices can be performed in near-optimal nondeterministic time O~(n^2). Since a classic algorithm due to Freivalds verifies correctness of matrix products probabilistically in time O(n^2), our question is a relaxation of the open problem of derandomizing Freivalds' algorithm. We discuss consequences of a positive or negative resolution of this problem and provide potential avenues towards resolving it. Particularly, we show that sufficiently fast deterministic verifiers for 3SUM or univariate polynomial identity testing yield faster deterministic verifiers for matrix multiplication. Furthermore, we present the partial algorithmic progress that distinguishing whether an integer matrix product is correct or contains between 1 and n erroneous entries can be performed in time O~(n^2) - interestingly, the difficult case of deterministic matrix product verification is not a problem of "finding a needle in the haystack", but rather cancellation effects in the presence of many errors. Our main technical contribution is a deterministic algorithm that corrects an integer matrix product containing at most t errors in time O~(sqrt{t} n^2 + t^2). To obtain this result, we show how to compute an integer matrix product with at most t nonzeroes in the same running time. This improves upon known deterministic output-sensitive integer matrix multiplication algorithms for t = Omega(n^{2/3}) nonzeroes, which is of independent interest.

We revisit the classic combinatorial pattern matching problem of finding a longest common subsequence (LCS). For strings x and y of length n, a textbook algorithm solves LCS in time O(n2), but although much effort has been spent, no -time algorithm is known. Recent work indeed shows that such an algorithm would refute the Strong Exponential Time Hypothesis (SETH) [Abboud, Backurs, Vassilevska Williams FOCS’15; Bringmann, Künnemann FOCS’15]. Despite the quadratic-time barrier, for over 40 years an enduring scientific interest continued to produce fast algorithms for LCS and its variations. Particular attention was put into identifying and exploiting input parameters that yield strongly subquadratic time algorithms for special cases of interest, e.g., differential file comparison. This line of research was successfully pursued until 1990, at which time significant improvements came to a halt. In this paper, using the lens of fine-grained complexity, our goal is to (1) justify the lack of further improvements and (2) determine whether some special cases of LCS admit faster algorithms than currently known. To this end, we provide a systematic study of the multivariate complexity of LCS, taking into account all parameters previously discussed in the literature: the input size n := max{|x|, |y|}, the length of the shorter string m := min{|x|, |y|}, the length L of an LCS of x and y, the numbers of deletions δ := m – L and Δ := n – L, the alphabet size, as well as the numbers of matching pairs M and dominant pairs d. For any class of instances defined by fixing each parameter individually to a polynomial in terms of the input size, we prove a SETH-based lower bound matching one of three known algorithms (up to lower order factors of the form no(1)). Specifically, we determine the optimal running time for LCS under SETH as (n + min{d, δΔ, δm})1±o(1). Polynomial improvements over this running time must necessarily refute SETH or exploit novel input parameters. We establish the same lower bound for any constant alphabet of size at least 3. For binary alphabet, we show a SETH-based lower bound of (n + min{d, δΔ, δΜ/n})1–o(1) and, motivated by difficulties to improve this lower bound, we design an -time algorithm, yielding again a matching bound. We feel that our systematic approach yields a comprehensive perspective on the well-studied multivariate complexity of LCS, and we hope to inspire similar studies of multivariate complexity landscapes for further polynomial-time problems.

Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed forms, becomes more and more relevant. Suppose we are given a compression of size n of data that originally has size N, and we want to solve a problem with time complexity T(·). The naive strategy of “decompress-and-solve” gives time T(N), whereas “the gold standard” is time T(n): to analyze the compression as efficiently as if the original data was small. We restrict our attention to data in the form of a string (text, files, genomes, etc.) and study the most ubiquitous tasks. While the challenge might seem to depend heavily on the specific compression scheme, most methods of practical relevance (Lempel-Ziv-family, dictionary methods, and others) can be unified under the elegant notion of Grammar-Compressions. A vast literature, across many disciplines, established this as an influential notion for Algorithm design. We introduce a direly needed framework for proving (conditional) lower bounds in this field, allowing us to assess whether decompress-and-solve can be improved, and by how much. Our main results are: (1) The O(nN√(log N/n)) bound for LCS and the O(min{N log N, nM}) bound for Pattern Matching with Wildcards are optimal up to No(1)factors, under the Strong Exponential Time Hypothesis. (Here, M denotes the uncompressed length of the compressed pattern.) (2) Decompress-and-solve is essentially optimal for ContextFree Grammar Parsing and RNA Folding, under the k-Clique conjecture. (3) We give an algorithm showing that decompress-and-solve is not optimal for Disjointness.

In the recent years, significant progress has been made in explaining apparent hardness of improving over naive solutions for many fundamental polynomially solvable problems. This came in the form of conditional lower bounds -- reductions from a problem assumed to be hard. These include 3SUM, All-Pairs Shortest Paths, SAT and Orthogonal Vectors, and others. In the (min,+)-convolution problem, the goal is to compute a sequence c, where c[k] = min_i a[i]+b[k-i], given sequences a and b. This can easily be done in O(n^2) time, but no O(n^{2-eps}) algorithm is known for eps > 0. In this paper we undertake a systematic study of the (min,+)-convolution problem as a hardness assumption. As the first step, we establish equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The (min,+)-convolution has been used as a building block in algorithms for many problems, notably problems in stringology. It has also already appeared as an ad hoc hardness assumption. We investigate some of these connections and provide new reductions and other results.

Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., The classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple O(n2) dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly sub quadratic time algorithms, i.e., No algorithms with running time O(n2 -- ε) for any ε > 0, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs, Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems. As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures.

We analyze the runtime of the (1 + λ) evolutionary algorithm (EA) on the classic royal road test function class. For a royal road function defined on bit-strings of length n having block sized ≥ log n + (c + 1 + ε) log d, we prove that the (1 + λ) EA with λ = Θ(nc) finds the optimum in an expected number of O(2d/dc· n/d log n/d) generations. Together with our lower bound of Ω(2d/dc), this shows that for royal road functions even very large offspring populations do not reduce the runtime significantly.

We analyze how the (1+λ) evolutionary algorithm (EA) optimizes linear pseudo-Boolean functions. We prove that it finds the optimum of any linear function within an expected number of O(1/λn log n+n) iterations. We also show that this bound is sharp for some functions, e.g., the binary value function. Hence unlike for the(1+1) EA, for the (1+λ) EA different linear functions may have run-times of different asymptotic order. The proof of our upper bound heavily relies on a number of classic and recent drift analysis methods. In particular, we show how to analyze a process displaying different types of drifts in different phases. Our work corrects a wrongfully claimed better asymptotic runtime in an earlier work~\cite{He10}.

We analyze the two existing algorithms to generate dependent randomized roundings for the bipartite edge weight rounding problem together with several newly proposed variants of these algorithms. For both the edge-based approach of Gandhi, Khuller, Parthasarathy, Srinivasan (FOCS 2002) and the bit-wise approach of Doerr (STACS 2006) we give a simple derandomization (guaranteeing the same rounding errors as the randomized versions achieve with positive probability). An experimental investigation on different types of random instances show that, contrary to the randomized rounding problem with disjoint cardinality constraints, the bit-wise approach is faster than the edge-based one, while the latter still achieves the best rounding errors. We propose a hybrid approach that, in terms of running time, combines advantages of the two previous approaches; in terms of rounding errors it seems a fair compromise. In all cases, the derandomized versions yield much better rounding errors than the randomized ones. We also test how the algorithms compare when used to solve different broadcast scheduling problems (as suggested by Gandhi et al.). Since this needs more random decisions than just in the rounding process, we need to partially re-prove previous results and simplify the corresponding algorithms to finally derive a derandomized version. Again, the derandomized versions give significantly better approximations than the randomized versions. We tested the algorithms on data taken from the Wikipedia access log. For the maximum throughput version of the problem, the derandomized algorithms compute solutions that are very close to the optimum of the linear relaxation. For the minimum average delay version, Gandhi et al. gave a (2, 1)-bicriteria algorithm, i.e., an algorithm which produces a 2-speed schedule with an average delay which on expectation is no worse than that of the 1-speed optimum. For this problem variant, while the performance guarantee of the algorithms certainly holds, we find that a simple greedy heuristic generally produces superior solutions.

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. At SODA 2008, three of the authors proposed a quasirandom variant. Here, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster (which was expected, though maybe not to this extent), but also that the runtime is more concentrated around the mean value (which is surprising given that much fewer random bits are used in the quasirandom process). These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that the particular structure of the lists has little influence on the efficiency. In particular, there is no problem if all nodes use an identical order to inform their neighbors.