Search

We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time $\widetilde{O}(n + t\sqrt{p_{\max}})$, where $n$ is the number of items, $t$ is the knapsack capacity, and $p_{\max}$ is the maximum item profit. This improves over the $\widetilde{O}(n + t \, p_{\max})$-time algorithm based on the convolution and prediction technique by Bateni et al.~(STOC 2018). Moreover, we give some evidence, based on a strengthening of the Min-Plus Convolution Hypothesis, that our running time might be optimal. Our algorithm uses two new technical tools, which might be of independent interest. First, we generalize the $\widetilde{O}(n^{1.5})$-time algorithm for bounded monotone min-plus convolution by Chi et al.~(STOC 2022) to the \emph{rectangular} case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to \emph{balanced} instances, where all items have nearly the same profit-to-weight ratio, up to a constant factor. Using these techniques, we can also obtain algorithms that run in time $\widetilde{O}(n + OPT\sqrt{w_{\max}})$, $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3}t^{2/3})$, and $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3} OPT^{2/3})$, where $OPT$ is the optimal total profit and $w_{\max}$ is the maximum item weight.

In an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/{\lceil k/2 \rceil}} + t)$ where $t$ is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph $G$ are colored by nodes in the pattern graph $H$, and we are only interested in subgraphs of $G$ that are isomorphic to the pattern $H$ and respect the colors. We study the problem of listing all $H$-subgraphs in the colored setting, for fixed pattern graphs $H$. As our main result, we determine all pattern graphs $H$ such that all $H$-subgraphs can be listed in subquadratic time $O(m^{2-\varepsilon} + t)$, where $t$ is the output size. Moreover, for each such subquadratic pattern $H$ we determine the smallest exponent $c(H)$ such that all $H$-subgraphs can be listed in time $O(m^{c(H)} + t)$. This is a vast generalization of the classic results on triangles and cycles. To prove this result, we design new listing algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. In our algorithms, we use a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. We also show the same results for two related problems: finding an $H$-subgraph of minimum total edge-weight in time $O(m^{c(H)})$, and enumerating all $H$-subgraphs in $O(m^{c(H)})$ preprocessing time and constant delay. Again we determine all pattern graphs $H$ that have complexity $c(H) < 2$, and for each such subquadratic pattern we determine the optimal complexity $c(H)$.

The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover's Distance under Translation ($\mathrm{EMDuT}$) is a translation-invariant version thereof. It minimizes the Earth Mover's Distance over all translations of one point set. For $\mathrm{EMDuT}$ in $\mathbb{R}^1$, we present an $\widetilde{\mathcal{O}}(n^2)$-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For $\mathrm{EMDuT}$ in $\mathbb{R}^d$, we present an $\widetilde{\mathcal{O}}(n^{2d+2})$-time algorithm for the $L_1$ and $L_\infty$ metric. We show that this dependence on $d$ is asymptotically tight, as an $n^{o(d)}$-time algorithm for $L_1$ or $L_\infty$ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems., Comment: Full version of the paper "Fine-Grained Complexity of Earth Mover's Distance under Translation" accepted for SoCG 2024

We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable shift in focus towards sublinear-time algorithms. Here, the task is typically formalized as the $(k, K)$-gap edit distance problem: Distinguish whether the edit distance of two strings is at most $k$ or more than $K$. Surprisingly, it is still possible to compute meaningful approximations in this challenging regime. Nevertheless, in almost all previous work, truly sublinear running time of $O(n^{1-\varepsilon})$ (for a constant $\varepsilon > 0$) comes at the price of at least polynomial gap $K \ge k \cdot n^{\Omega(\varepsilon)}$. Only recently, [Bringmann, Cassis, Fischer, and Nakos; STOC'22] broke through this barrier and solved the sub-polynomial $(k, k^{1+o(1)})$-gap edit distance problem in time $O(n/k + k^{4+o(1)})$, which is truly sublinear if $n^{\Omega(1)} \le k \le n^{\frac14-\Omega(1)}$.The $n/k$ term is inevitable (already for Hamming distance), but it remains an important task to optimize the $\mathrm{poly}(k)$ term and, in general, solve the $(k, k^{1+o(1)})$-gap edit distance problem in sublinear-time for larger values of $k$. In this work, we design an improved algorithm for the $(k, k^{1+o(1)})$-gap edit distance problem in sublinear time $O(n/k + k^{2+o(1)})$, yielding a significant quadratic speed-up over the previous $O(n/k + k^{4+o(1)})$-time algorithm. Notably, our algorithm is unconditionally almost-optimal (up to subpolynomial factors) in the regime where $k \leq n^{\frac13}$ and improves upon the state of the art for $k \leq n^{\frac12-o(1)}$., Comment: To appear in SODA'24. Shortened abstract for arXiv

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., Comment: 31 pages, Accepted at ITCS

The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensitive alternative to the \frechet distance. For static curves of at most $n$ points, the DTW distance can be computed in $O(n^2)$ time in constant dimension. This tightly matches a SETH-based lower bound, even for curves in $\mathbb{R}^1$. In this work, we study \emph{dynamic} algorithms for the DTW distance. Here, the goal is to design a data structure that can be efficiently updated to accommodate local changes to one or both curves, such as inserting or deleting vertices and, after each operation, reports the updated DTW distance. We give such a data structure with update and query time $O(n^{1.5} \log n)$, where $n$ is the maximum length of the curves. As our main result, we prove that our data structure is conditionally \emph{optimal}, up to subpolynomial factors. More precisely, we prove that, already for curves in $\mathbb{R}^1$, there is no dynamic algorithm to maintain the DTW distance with update and query time~\makebox{$O(n^{1.5 - \delta})$} for any constant $\delta > 0$, unless the Negative-$k$-Clique Hypothesis fails. In fact, we give matching upper and lower bounds for various trade-offs between update and query time, even in cases where the lengths of the curves differ., Comment: To appear at SODA24

Subset Sum Ratio is the following optimization problem: Given a set of $n$ positive numbers $I$, find disjoint subsets $X,Y \subseteq I$ minimizing the ratio $\max\{\Sigma(X)/\Sigma(Y),\Sigma(Y)/\Sigma(X)\}$, where $\Sigma(Z)$ denotes the sum of all elements of $Z$. Subset Sum Ratio is an optimization variant of the Equal Subset Sum problem. It was introduced by Woeginger and Yu in '92 and is known to admit an FPTAS [Bazgan, Santha, Tuza '98]. The best approximation schemes before this work had running time $O(n^4/\varepsilon)$ [Melissinos, Pagourtzis '18], $\tilde O(n^{2.3}/\varepsilon^{2.6})$ and $\tilde O(n^2/\varepsilon^3)$ [Alonistiotis et al. '22]. In this work, we present an improved approximation scheme for Subset Sum Ratio running in time $O(n / \varepsilon^{0.9386})$. Here we assume that the items are given in sorted order, otherwise we need an additional running time of $O(n \log n)$ for sorting. Our improved running time simultaneously improves the dependence on $n$ to linear and the dependence on $1/\varepsilon$ to sublinear. For comparison, the related Subset Sum problem admits an approximation scheme running in time $O(n/\varepsilon)$ [Gens, Levner '79]. If one would achieve an approximation scheme with running time $\tilde O(n / \varepsilon^{0.99})$ for Subset Sum, then one would falsify the Strong Exponential Time Hypothesis [Abboud, Bringmann, Hermelin, Shabtay '19] as well as the Min-Plus-Convolution Hypothesis [Bringmann, Nakos '21]. We thus establish that Subset Sum Ratio admits faster approximation schemes than Subset Sum. This comes as a surprise, since at any point in time before this work the best known approximation scheme for Subset Sum Ratio had a worse running time than the best known approximation scheme for Subset Sum., Comment: Accepted at SODA'24, 22 pages

What is the time complexity of matrix multiplication of sparse integer matrices with $m_{in}$ nonzeros in the input and $m_{out}$ nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of $m_{in}$ vs. $m_{out}$, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication. Our main contribution is a new algorithm that reduces sparse matrix multiplication to dense (but smaller) rectangular matrix multiplication. Our running time thus depends on the optimal exponent $\omega(a,b,c)$ of multiplying dense $n^a\times n^b$ by $n^b\times n^c$ matrices. We discover that when $m_{out}=\Theta(m_{in}^r)$ the time complexity of sparse matrix multiplication is $O(m_{in}^{\sigma+\epsilon})$, for all $\epsilon > 0$, where $\sigma$ is the solution to the equation $\omega(\sigma-1,2-\sigma,1+r-\sigma)=\sigma$. No matter what $\omega(\cdot,\cdot,\cdot)$ turns out to be, and for all $r\in(0,2)$, the new bound beats the state of the art, and we provide evidence that it is optimal based on the complexity of the all-edge triangle problem. In particular, in terms of the input plus output size $m = m_{in} + m_{out}$ our algorithm runs in time $O(m^{1.3459})$. Even for Boolean matrices, this improves over the previous $m^{\frac{2\omega}{\omega+1}+\epsilon}=O(m^{1.4071})$ bound [Amossen, Pagh; 2009], which was a natural barrier since it coincides with the longstanding bound of all-edge triangle in sparse graphs [Alon, Yuster, Zwick; 1994]. We find it interesting that matrix multiplication can be solved faster than triangle detection in this natural setting. In fact, we establish an equivalence to a special case of the all-edge triangle problem.

The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight $w_{\mathrm{max}}$ and the number of items $n$. A conditional lower bound rules out that Knapsack can be solved in time $O((n+w_{\mathrm{max}})^{2-\delta})$ for any $\delta > 0$ [Cygan, Mucha, Wegrzycki, Wlodarczyk'17, K\"unnemann, Paturi, Schneider'17]. This raised the question whether Knapsack can be solved in time $\tilde O((n+w_{\mathrm{max}})^2)$. This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time $\tilde O(n^3 w_{\mathrm{max}}^2)$ [Tamir'09], $\tilde O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^3)$ [Bateni, Hajiaghayi, Seddighin, Stein'18], $O(n^2 w_{\mathrm{max}}^2)$ and $\tilde O(n w_{\mathrm{max}}^2)$ [Eisenbrand and Weismantel'18], $O(n + w_{\mathrm{max}}^3)$ [Polak, Rohwedder, Wegrzycki'21], and very recently $\tilde O(n + w_{\mathrm{max}}^{12/5})$ [Chen, Lian, Mao, Zhang'23]. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time $\tilde O(n + w_{\mathrm{max}}^2)$, which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem., Comment: 28 pages, accepted at STOC'24

We revisit the classic 0-1-Knapsack problem, in which we are given $n$ items with their weights and profits as well as a weight budget $W$, and the goal is to find a subset of items of total weight at most $W$ that maximizes the total profit. We study pseudopolynomial-time algorithms parameterized by the largest profit of any item $p_{\max}$, and the largest weight of any item $w_{\max}$. Our main result are algorithms for 0-1-Knapsack running in time $\tilde{O}(n\,w_\max\,p_\max^{2/3})$ and $\tilde{O}(n\,p_\max\,w_\max^{2/3})$, improving upon an algorithm in time $O(n\,p_\max\,w_\max)$ by Pisinger [J. Algorithms '99]. In the regime $p_\max \approx w_\max \approx n$ (and $W \approx \mathrm{OPT} \approx n^2$) our algorithms are the first to break the cubic barrier $n^3$. To obtain our result, we give an efficient algorithm to compute the min-plus convolution of near-convex functions. More precisely, we say that a function $f \colon [n] \mapsto \mathbf{Z}$ is $\Delta$-near convex with $\Delta \geq 1$, if there is a convex function $\breve{f}$ such that $\breve{f}(i) \leq f(i) \leq \breve{f}(i) + \Delta$ for every $i$. We design an algorithm computing the min-plus convolution of two $\Delta$-near convex functions in time $\tilde{O}(n\Delta)$. This tool can replace the usage of the prediction technique of Bateni, Hajiaghayi, Seddighin and Stein [STOC '18] in all applications we are aware of, and we believe it has wider applicability.

In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear $O(m \log^8(n) \log(W))$-time algorithm for negative-weight SSSP, where $W$ is an upper bound on the magnitude of the smallest negative-weight edge. In this work we improve the running time to $O(m \log^2(n) \log(nW) \log\log n)$, which is an improvement by nearly six log-factors. Some of these log-factors are easy to shave (e.g. replacing the priority queue used in Dijkstra's algorithm), while others are significantly more involved (e.g. to find negative cycles we design an algorithm reminiscent of noisy binary search and analyze it with drift analysis). As side results, we obtain an algorithm to compute the minimum cycle mean in the same running time as well as a new construction for computing Low-Diameter Decompositions in directed graphs.

The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an $n^{1/2}$-regular graph is $n^{2-o(1)}$-hard under the 3-SUM conjecture even when the number of short cycles is small; namely, when the number of $k$-cycles is $O(n^{k/2+\gamma})$ for $\gamma<1/2$. Abboud et al. achieve $\gamma\geq 1/4$ by applying structure vs. randomness arguments on graphs. In this paper, we take a step back and apply conceptually similar arguments on the numbers of the 3-SUM problem. Consequently, we achieve the best possible $\gamma=0$ and the following lower bounds under the 3-SUM conjecture: * Approximate distance oracles: The seminal Thorup-Zwick distance oracles achieve stretch $2k\pm O(1)$ after preprocessing a graph in $O(m n^{1/k})$ time. For the same stretch, and assuming the query time is $n^{o(1)}$ Abboud et al. proved an $\Omega(m^{1+\frac{1}{12.7552 \cdot k}})$ lower bound on the preprocessing time; we improve it to $\Omega(m^{1+\frac1{2k}})$ which is only a factor 2 away from the upper bound. We also obtain tight bounds for stretch $2+o(1)$ and $3-\epsilon$ and higher lower bounds for dynamic shortest paths. * Listing 4-cycles: Abboud et al. proved the first super-linear lower bound for listing all 4-cycles in a graph, ruling out $(m^{1.1927}+t)^{1+o(1)}$ time algorithms where $t$ is the number of 4-cycles. We settle the complexity of this basic problem by showing that the $\widetilde{O}(\min(m^{4/3},n^2) +t)$ upper bound is tight up to $n^{o(1)}$ factors. Our results exploit a rich tool set from additive combinatorics, most notably the Balog-Szemer\'edi-Gowers theorem and Rusza's covering lemma. A key ingredient that may be of independent interest is a subquadratic algorithm for 3-SUM if one of the sets has small doubling., Comment: Abstract shortened to fit arXiv requirements

We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with linear preprocessing time and constant delay. Despite the basic nature of this problem, it was shown only recently that UCQs can be solved within these time bounds if they admit free-connex union extensions, even if all individual CQs in the union are intractable with respect to the same complexity measure. Our goal is to understand whether there exist additional tractable UCQs, not covered by the currently known algorithms. As a first step, we show that some previously unclassified UCQs are hard using the classic 3SUM hypothesis, via a known reduction from 3SUM to triangle listing in graphs. As a second step, we identify a question about a variant of this graph task that is unavoidable if we want to classify all self-join-free UCQs: is it possible to decide the existence of a triangle in a vertex-unbalanced tripartite graph in linear time? We prove that this task is equivalent in hardness to some family of UCQs. Finally, we show a dichotomy for unions of two self-join-free CQs if we assume the answer to this question is negative. In conclusion, this paper pinpoints a computational barrier in the form of a single decision problem that is key to advancing our understanding of the enumeration complexity of many UCQs. Without a breakthrough for unbalanced triangle detection, we have no hope of finding an efficient algorithm for additional unions of two self-join-free CQs. On the other hand, a sufficiently efficient unbalanced triangle detection algorithm can be turned into an efficient algorithm for a family of UCQs currently not known to be tractable.

We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$, where $n$ is the number of items, $W$ is the weight budget, and $OPT$ is the optimal profit. We present an algorithm running in time $\widetilde{O}(n + (W + OPT)^{1.5})$. This improves the running time in case $n,W,OPT$ are roughly equal. * Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n \cdot p_{\max}, n \cdot w_{\max}, p_{\max}^2, w_{\max}^2\})$ [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '20], where $n$ is the number of items, $w_{\max}$ is the largest weight of any item, and $p_{\max}$ is the largest profit of any item. We present an algorithm running in time $\widetilde{O}(n + (p_{\max} + w_{\max})^{1.5})$, giving a similar improvement as for 0-1-Knapsack. * Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time $\widetilde{O}(\min\{n/\varepsilon, n + 1/\varepsilon^2\})$ [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint. We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time $\widetilde{O}(n + 1/\varepsilon^{1.5})$. Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time $O(n^{1.5})$ [Chi,Duan,Xie,Zhang '22] (in contrast to the conjectured $n^{2-o(1)}$ lower bound for the general case)., Comment: Shortened abstract. Appears at ICALP '22

We consider the unlabeled motion-planning problem of $m$ unit-disc robots moving in a simple polygonal workspace of $n$ edges. The goal is to find a motion plan that moves the robots to a given set of $m$ target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time $O(n \log n + mn + m^2)$ if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance $4$ apart, any two target positions are at least distance $4$ apart, and any pair of a start and a target positions is at least distance $3$ apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary., Comment: A shorter version of this paper appeared in the Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022)

We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the $(k, K)$-gap edit distance problem, the goal is to distinguish whether the edit distance of two strings is at most $k$ or at least $K$. We obtain the following results: * After preprocessing one string in time $n^{1+o(1)}$, we can solve $(k, k \cdot n^{o(1)})$-gap edit distance in time $(n/k + k) \cdot n^{o(1)}$. * After preprocessing both strings separately in time $n^{1+o(1)}$, we can solve $(k, k \cdot n^{o(1)})$-gap edit distance in time $k \cdot n^{o(1)}$. Both results improve upon some previously best known result, with respect to either the gap or the query time or the preprocessing time. Our algorithms build on the framework by Andoni, Krauthgamer and Onak (FOCS '10) and the recent sublinear-time algorithm by Bringmann, Cassis, Fischer and Nakos (STOC '22). We replace many complicated parts in their algorithm by faster and simpler solutions which exploit the preprocessing., Comment: Appears at ICALP '22

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, MaxSP$_k$ denotes the class of $O(m^k)$-time problems of the form $\max_{x_1,\dots, x_k} \#\{y:\phi(x_1,\dots,x_k,y)\}$ where $\phi$ 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 MAX3SAT, we show that for any MaxSP$_k$ problem definable by a quantifier-free $m$-edge graph formula $\phi$, the best possible approximation guarantee in faster-than-exhaustive-search time $O(m^{k-\delta})$ falls into one of four categories: * optimizable to exactness in time $O(m^{k-\delta})$, * an (inefficient) approximation scheme, i.e., a $(1+\epsilon)$-approximation in time $O(m^{k-f(\epsilon)})$, * a (fixed) constant-factor approximation in time $O(m^{k-\delta})$, or * an $m^\epsilon$-approximation in time $O(m^{k-f(\epsilon)})$. 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 rule out approximation schemes for a large class of problems admitting constant-factor approximations, under the Sparse MAX3SAT hypothesis posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we find: (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., Comment: Appears at ICALP '22, abstract shortened to fit arXiv requirements

We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost $k$-cycle free graphs, for any constant $k\geq 4$. Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many $4$- or $5$-cycles in a worst-case instance had been the obstacle towards resolving major open questions. Hardness of approximation: Are there distance oracles with $m^{1+o(1)}$ preprocessing time and $m^{o(1)}$ query time that achieve a constant approximation? Existing algorithms with such desirable time bounds only achieve super-constant approximation factors, while only $3-\epsilon$ factors were conditionally ruled out (P\u{a}tra\c{s}cu, Roditty, and Thorup; FOCS 2012). We prove that no $O(1)$ approximations are possible, assuming the $3$-SUM or APSP conjectures. In particular, we prove that $k$-approximations require $\Omega(m^{1+1/ck})$ time, which is tight up to the constant $c$. The lower bound holds even for the offline version where we are given the queries in advance, and extends to other problems such as dynamic shortest paths. The $4$-Cycle problem: An infamous open question in fine-grained complexity is to establish any surprising consequences from a subquadratic or even linear-time algorithm for detecting a $4$-cycle in a graph. We prove that $\Omega(m^{1.1194})$ time is needed for $k$-cycle detection for all $k\geq 4$, unless we can detect a triangle in $\sqrt{n}$-degree graphs in $O(n^{2-\delta})$ time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms., Comment: The abstract was slightly shortened to meet arXiv requirements. Appears in STOC 2022

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves $\pi, \sigma$ in $\mathbb{R}^d$, it provides a robust, outlier-insensitive alternative to the Fr\'echet distance. However, like the Fr\'echet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of $\pi$ and $\sigma$ 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_1$ norm in $\mathbb{R}^d$, we provide an $\mathcal{O}(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 $\mathbb{R}^2$, we show that a simple problem-specific insight leads to a $(1+\varepsilon)$-approximation in time $\mathcal{O}(n^3/\varepsilon^2)$. We then show how to obtain a subcubic $\widetilde{\mathcal{O}}(n^{2.5}/\varepsilon^2)$ 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., Comment: Full version of SoCG '22 paper

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-\delta})$ for some $\delta>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., Comment: Full version of SoCG '22 paper

We revisit the task of computing the edit distance in sublinear time. In the $(k,K)$-gap edit distance problem the task is to distinguish whether the edit distance of two strings is at most $k$ or at least $K$. It has been established by Goldenberg, Krauthgamer and Saha (FOCS '19), with improvements by Kociumaka and Saha (FOCS '20), that the $(k,k^2)$-gap problem can be solved in time $\widetilde O(n/k+\operatorname{poly}(k))$. One of the most natural questions in this line of research is whether the $(k,k^2)$-gap is best-possible for the running time $\widetilde O(n/k+\operatorname{poly}(k))$. In this work we answer this question by significantly improving the gap. Specifically, we show that in time $O(n/k+\operatorname{poly}(k))$ we can even solve the $(k,k^{1+o(1)})$-gap problem. This is the first algorithm that breaks the $(k,k^2)$-gap in this running time. Our algorithm is almost optimal in the following sense: In the low distance regime ($k\le n^{0.19}$) our running time becomes $O(n/k)$, which matches a known $n/k^{1+o(1)}$ lower bound for the $(k,k^{1+o(1)})$-gap problem up to lower order factors. Our result also reveals a surprising similarity of Hamming distance and edit distance in the low distance regime: For both, the $(k,k^{1+o(1)})$-gap problem has time complexity $n/k^{1\pm o(1)}$ for small $k$. In contrast to previous work, which employed a subsampled variant of the Landau-Vishkin algorithm, we instead build upon the algorithm of Andoni, Krauthgamer and Onak (FOCS '10). We first simplify their approach and then show how to to effectively prune their computation tree in order to obtain a sublinear-time algorithm in the given time bound. Towards that, we use a variety of structural insights on the (local and global) patterns that can emerge during this process and design appropriate property testers to effectively detect these patterns., Comment: Appeared at STOC'22. Abstract shortened to fit arXiv requirements. Version 2: Fixed an inaccuracy

We consider the task of lexicographic direct access to query answers. That is, we want to simulate an array containing the answers of a join query sorted in a lexicographic order chosen by the user. A recent dichotomy showed for which queries and orders this task can be done in polylogarithmic access time after quasilinear preprocessing, but this dichotomy does not tell us how much time is required in the cases classified as hard. We determine the preprocessing time needed to achieve polylogarithmic access time for all join queries and all lexicographical orders. To this end, we propose a decomposition-based general algorithm for direct access on join queries. We then explore its optimality by proving lower bounds for the preprocessing time based on the hardness of a certain online Set-Disjointness problem, which shows that our algorithm's bounds are tight for all lexicographic orders on join queries. Then, we prove the hardness of Set-Disjointness based on the Zero-Clique Conjecture which is an established conjecture from fine-grained complexity theory. Interestingly, while proving our lower bound, we show that self-joins do not affect the complexity of direct access (up to logarithmic factors). Our algorithm can also be used to solve queries with projections and relaxed order requirements, though in these cases, its running time not necessarily optimal. We also show that similar techniques to those used in our lower bounds can be used to prove that, for enumerating answers to Loomis-Whitney joins, it is not possible to significantly improve upon trivially computing all answers at preprocessing. This, in turn, gives further evidence (based on the Zero-Clique Conjecture) to the enumeration hardness of self-join free cyclic joins with respect to linear preprocessing and constant delay.

Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectures. This area has been thriving in the last decade, leading to conditionally best-possible algorithms for a wide variety of problems on graphs, strings, numbers etc. This article is an introduction to fine-grained lower bounds in computational geometry, with a focus on lower bounds for polynomial-time problems based on the Orthogonal Vectors Hypothesis. Specifically, we discuss conditional lower bounds for nearest neighbor search under the Euclidean distance and Fr\'echet distance., Comment: Written version of a tutorial talk given at a special session of CiE'21

In the classical Subset Sum problem we are given a set $X$ and a target $t$, and the task is to decide whether there exists a subset of $X$ which sums to $t$. A recent line of research has resulted in $\tilde{O}(t)$-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time $O(n \cdot |\mathcal{S}(X,t)|)$, where $\mathcal{S}(X,t)$ is the set of all subset sums of $X$ that are smaller than $t$. Furthermore, all known pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set $\mathcal{S}(X,t)$. As the aforementioned two running times are incomparable, in this paper we ask whether one can achieve the best of both worlds: running time $\tilde{O}(|\mathcal{S}(X,t)|)$. In particular, we ask whether $\mathcal{S}(X,t)$ can be computed in near-linear time in the output-size. Using a diverse toolkit containing techniques such as color coding, sparse recovery, and sumset estimates, we make considerable progress towards this question and design an algorithm running in time $\tilde{O}(|\mathcal{S}(X,t)|^{4/3})$. Central to our approach is the study of top-$k$-convolution, a natural problem of independent interest: given sparse polynomials with non-negative coefficients, compute the lowest $k$ non-zero monomials of their product. We design an algorithm running in time $\tilde{O}(k^{4/3})$, by a combination of sparse convolution and sumset estimates considered in Additive Combinatorics. Moreover, we provide evidence that going beyond some of the barriers we have faced requires either an algorithmic breakthrough or possibly new techniques from Additive Combinatorics on how to pass from information on restricted sumsets to information on unrestricted sumsets., Comment: 40 pages, full version of STOC'20 paper

We study the $c$-approximate near neighbor problem under the continuous Fr\'echet distance: Given a set of $n$ polygonal curves with $m$ vertices, a radius $\delta > 0$, and a parameter $k \leq m$, we want to preprocess the curves into a data structure that, given a query curve $q$ with $k$ vertices, either returns an input curve with Fr\'echet distance at most $c\cdot \delta$ to $q$, or returns that there exists no input curve with Fr\'echet distance at most $\delta$ to $q$. We focus on the case where the input and the queries are one-dimensional polygonal curves -- also called time series -- and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any $0 < \varepsilon \leq 1$ an approximation factor of $(1+\varepsilon)$ can be achieved within the same asymptotic time bounds as the previously best result for $(2+\varepsilon)$. Moreover, we show that an approximation factor of $(2+\varepsilon)$ can be obtained by using preprocessing time and space $O(nm)$, which is linear in the input size, and query time in $O(\frac{1}{\varepsilon})^{k+2}$, where the previously best result used preprocessing time in $n \cdot O(\frac{m}{\varepsilon k})^k$ and query time in $O(1)^k$. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of $k$. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest., Comment: to appear at SODA 2020

Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor., Comment: 23 pages

We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier $k$-sparse vector $\widehat{x} \in \mathbb{C}^{n^d}$ from observing its time domain representation $x$. In the exact $k$-sparse case the best known dimension-independent algorithm runs in near cubic time in $k$ and it is unclear whether a faster algorithm like in low dimensions is possible. Beyond that, all known approaches either suffer from an exponential dependence on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$ for $N=n^d$. Our work aims to address the above issues. First, we provide a translation/reduction of the exactly $k$-sparse FT problem to a concrete tree exploration task which asks to recover $k$ leaves in a full binary tree under certain exploration rules. Subsequently, we provide (a) an almost quadratic in $k$ time algorithm for this task, and (b) evidence that a strongly subquadratic time for Sparse FT via this approach is likely impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse FT) which is a core routine in the aforementioned translation. Thus, our results combined can be viewed as an almost complete understanding of this approach, which is the only known approach that yields sublinear time dimension-independent Sparse FT algorithms. Subsequently, we provide a robustification of our algorithm, yielding a robust cubic time algorithm under bounded $\ell_2$ noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas.

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) : \phi(x_1,\dots,x_k, y_1,\dots,y_\ell) \}$, where $\phi$ 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-\delta})$, 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., Comment: Full version of APPROX'21 paper, abstract shortened to fit ArXiv requirements

We consider the classic problem of computing the Longest Common Subsequence (LCS) of two strings of length $n$. While a simple quadratic algorithm has been known for the problem for more than 40 years, no faster algorithm has been found despite an extensive effort. The lack of progress on the problem has recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15] and Bringmann and K\"unnemann [FOCS'15] who proved that there is no subquadratic algorithm unless the Strong Exponential Time Hypothesis fails. This has led the community to look for subquadratic approximation algorithms for the problem. Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive $O(n^{\varepsilon/2})$-approximation algorithm with running time $\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 < \varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a $O(n^{0.497956})$-approximation in expectation; improving upon the naive $O(\sqrt{n})$-approximation for the first time. In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$ computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an $\tilde{O}(n^{0.4})$-approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time $O(n^{2-\varepsilon})$, improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$, and (3) instead of only in expectation, succeeds with high probability., Comment: full version of ICALP'21 paper, abstract shortened to fit Arxiv requirements

Computing the convolution $A\star B$ of two length-$n$ vectors $A,B$ is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, and from 3SUM to All-Pairs Shortest Paths. These applications often come in the form of nonnegative convolution, where the entries of $A,B$ are nonnegative integers. The classical algorithm to compute $A\star B$ uses the Fast Fourier Transform and runs in time $O(n\log n)$. However, often $A$ and $B$ satisfy sparsity conditions, and hence one could hope for significant improvements. The ideal goal is an $O(k\log k)$-time algorithm, where $k$ is the number of non-zero elements in the output, i.e., the size of the support of $A\star B$. This problem is referred to as sparse nonnegative convolution, and has received considerable attention in the literature; the fastest algorithms to date run in time $O(k\log^2 n)$. The main result of this paper is the first $O(k\log k)$-time algorithm for sparse nonnegative convolution. Our algorithm is randomized and assumes that the length $n$ and the largest entry of $A$ and $B$ are subexponential in $k$. Surprisingly, we can phrase our algorithm as a reduction from the sparse case to the dense case of nonnegative convolution, showing that, under some mild assumptions, sparse nonnegative convolution is equivalent to dense nonnegative convolution for constant-error randomized algorithms. Specifically, if $D(n)$ is the time to convolve two nonnegative length-$n$ vectors with success probability $2/3$, and $S(k)$ is the time to convolve two nonnegative vectors with output size $k$ with success probability $2/3$, then $S(k)=O(D(k)+k(\log\log k)^2)$. Our approach uses a variety of new techniques in combination with some old machinery from linear sketching and structured linear algebra, as well as new insights on linear hashing, the most classical hash function., Comment: 44 pages, appears in STOC 2021

The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time $O(n^{tw(H)+1})$ [Alon, Yuster, Zwick'95], where $n$ is the number of vertices of the host graph $G$. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of $O(n^{tw(H)+1-\varepsilon})$ or even faster (e.g. for $k$-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time $n^{o(tw(H) / \log(tw(H)))}$ for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs $H$ that require time $n^{tw(H)+1-o(1)}$. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth $t$: For any $\varepsilon > 0$ there exists $t \ge 3$ and a pattern graph $H$ of treewidth $t$ such that Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$ Subgraph Isomorphism on pattern $H$ has no algorithm running in time $O(n^{t+1-\varepsilon})$. In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for $tw < 3$, (3) Subgraph Isomorphism parameterized by pathwidth, and (4) a weighted problem variant., Comment: Full version of ICALP 2021 paper, 55 pages, abstract shortened to fit ArXiv requirements

We consider the problem of computing the Boolean convolution (with wraparound) of $n$~vectors of dimension $m$, or, equivalently, the problem of computing the sumset $A_1+A_2+\ldots+A_n$ for $A_1,\ldots,A_n \subseteq \mathbb{Z}_m$. Boolean convolution formalizes the frequent task of combining two subproblems, where the whole problem has a solution of size $k$ if for some $i$ the first subproblem has a solution of size~$i$ and the second subproblem has a solution of size $k-i$. Our problem formalizes a natural generalization, namely combining solutions of $n$ subproblems subject to a modular constraint. This simultaneously generalises Modular Subset Sum and Boolean Convolution (Sumset Computation). Although nearly optimal algorithms are known for special cases of this problem, not even tiny improvements are known for the general case. We almost resolve the computational complexity of this problem, shaving essentially a factor of $n$ from the running time of previous algorithms. Specifically, we present a \emph{deterministic} algorithm running in \emph{almost} linear time with respect to the input plus output size $k$. We also present a \emph{Las Vegas} algorithm running in \emph{nearly} linear expected time with respect to the input plus output size $k$. Previously, no deterministic or randomized $o(nk)$ algorithm was known. At the heart of our approach lies a careful usage of Kneser's theorem from Additive Combinatorics, and a new deterministic almost linear output-sensitive algorithm for non-negative sparse convolution. In total, our work builds a solid toolbox that could be of independent interest., Comment: ICALP 2021, 17 pages

Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size $n$ and $m$, the Hausdorff distance under translation can be computed in time $\tilde O(nm)$ for the $L_1$ and $L_\infty$ norm [Chew, Kedem SWAT'92] and $\tilde O(nm (n+m))$ for the $L_2$ norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of $(nm)^{1-o(1)}$ for $L_1$ and $L_\infty$ (and all other $L_p$ norms) assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of $n^{2-o(1)}$ for $L_2$ in the imbalanced case of $m = O(1)$ assuming the 3SUM Hypothesis., Comment: to be published at JoCG

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 \ll 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(\rm{inputsize})$, 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 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., Comment: NeurIPS'20, 20 pages

In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all input numbers $\Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $\tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,\rm{mx}_X,\Sigma_X$ for which dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can be ignored) and $t \le \Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time $\tilde{O}(n)$ if $t \gg \rm{mx}_X \Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t \ll \rm{mx}_X \Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds., Comment: full version of SODA'21 paper, 36 pages

We revisit the Subset Sum problem over the finite cyclic group $\mathbb{Z}_m$ for some given integer $m$. A series of recent works has provided near-optimal algorithms for this problem under the Strong Exponential Time Hypothesis. Koiliaris and Xu (SODA'17, TALG'19) gave a deterministic algorithm running in time $\tilde{O}(m^{5/4})$, which was later improved to $O(m \log^7 m)$ randomized time by Axiotis et al. (SODA'19). In this work, we present two simple algorithms for the Modular Subset Sum problem running in near-linear time in $m$, both efficiently implementing Bellman's iteration over $\mathbb{Z}_m$. The first one is a randomized algorithm running in time $O(m \log^2 m)$, that is based solely on rolling hash and an elementary data-structure for prefix sums; to illustrate its simplicity we provide a short and efficient implementation of the algorithm in Python. Our second solution is a deterministic algorithm running in time $O(m\ \mathrm{polylog}\ m)$, that uses dynamic data structures for string manipulation. We further show that the techniques developed in this work can also lead to simple algorithms for the All Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matching the near-optimal running time of $\tilde{O}(n^2)$ provided in the recent work of Duan et al. (ICALP'19)., Comment: accepted at SOSA'21

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\'echet 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\'echet distance, we perform algorithm engineering for the Fr\'echet 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\'echet 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\'echet distance under translation in applications, whereas previous approaches would have been computationally infeasible., Comment: A shorter version was accepted at ESA 2020

Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers $X_i$ has a subset that sums up to the target integer $t_i$. We prove that this problem cannot be solved in time $\tilde{O}((N \cdot t_{max})^{1-\epsilon})$, for $t_{max}=\max_i t_i$ and any $\epsilon > 0$, assuming the $\forall \exists$ Strong Exponential Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude $\tilde{O}(n+P_{max} \cdot n^{1-\epsilon})$-time algorithms for several scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based on $\forall \exists$-SETH. These include classical problems such as $1||\sum w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy jobs on two identical parallel machines., Comment: 14 pages, ICALP'20

This paper is concerned with the $1||\sum p_jU_j$ problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also a very important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The fastest known pseudo-polynomial time algorithm for the problem is the famous Lawler and Moore algorithm which runs in $O(P \cdot n)$ time, where $P$ is the total processing time of all $n$ jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for $1||\sum p_jU_j$, each improving on Lawler and Moore's algorithm in a different scenario. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, while for the first algorithm we define a new "skewed" version of $(\max,\min)$-convolution which is interesting in its own right., Comment: 12 pages; ICALP'20 (A)

Approximating Subset Sum is a classic and fundamental problem in computer science and mathematical optimization. The state-of-the-art approximation scheme for Subset Sum computes a $(1-\varepsilon)$-approximation in time $\tilde{O}(\min\{n/\varepsilon, n+1/\varepsilon^2\})$ [Gens, Levner'78, Kellerer et al.'97]. In particular, a $(1-1/n)$-approximation can be computed in time $O(n^2)$. We establish a connection to Min-Plus-Convolution, a problem that is of particular interest in fine-grained complexity theory and can be solved naively in time $O(n^2)$. Our main result is that computing a $(1-1/n)$-approximation for Subset Sum is subquadratically equivalent to Min-Plus-Convolution. Thus, assuming the Min-Plus-Convolution conjecture from fine-grained complexity theory, there is no approximation scheme for Subset Sum with strongly subquadratic dependence on $n$ and $1/\varepsilon$. In the other direction, our reduction allows us to transfer known lower order improvements from Min-Plus-Convolution to Subset Sum, which yields a mildly subquadratic randomized approximation scheme. This adds the first approximation problem to the list of problems that are equivalent to Min-Plus-Convolution. For the related Partition problem, an important special case of Subset Sum, the state of the art is a randomized approximation scheme running in time $\tilde{O}(n+1/\varepsilon^{5/3})$ [Mucha~et~al.'19]. We adapt our reduction from Subset Sum to Min-Plus-Convolution to obtain a related reduction from Partition to Min-Plus-Convolution. This yields an improved approximation scheme for Partition running in time $\tilde{O}(n + 1/\varepsilon^{3/2})$. Our algorithm is the first deterministic approximation scheme for Partition that breaks the quadratic barrier., Comment: accepted at SODA'21, 28 pages

Zwick's $(1+\varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $\widetilde{O}(\frac{n^\omega}{\varepsilon} \log{W})$, where $\omega \le 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. Since Zwick's algorithm uses the scaling technique, it has a factor $\log W$ in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of $W$; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time $O(\frac{n^\omega}{\varepsilon} \text{polylog}(\frac{n}{\varepsilon}))$ for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time $O(n^{\frac{\omega + 3}{2}} \varepsilon^{-1} \text{polylog}(\frac{n}{\varepsilon}))$. This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than $\omega$: Any improvement over our exponent $\frac{\omega + 3}{2}$ would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent., Comment: Presented at STOC'19. Full Version. 35 pages

The Fr\'echet 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\'echet 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\'echet distance. The bottleneck of the top three implementations turned out to be precisely the decision procedure for the Fr\'echet distance. In this work, we present a fast, certifying implementation for deciding the Fr\'echet 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\'echet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fr\'echet 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 $\tilde{\cal O}(n^{5})$ [Ben Avraham, Kaplan, Sharir '15]. This is achieved by constructing an arrangement of disks of size ${\cal O}(n^{4})$, and then traversing its faces while updating reachability in a directed grid graph of size $N := {\cal O}(n^2)$, which can be done in time $\tilde{\cal O}(\sqrt{N})$ 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 $\tilde{\cal O}(\sqrt{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 $\tilde{\cal O}(N^{1/3})$ per update, resulting in an improved running time of $\tilde{\cal O}(n^{4.66...})$ for the discrete Fr\'echet distance under translation. Second, we provide evidence that constructing the arrangement of size ${\cal O}(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\'echet distance under translation, assuming the Strong Exponential Time Hypothesis., Comment: Published at TALG

We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size $|\Sigma|$. For the problem of deciding whether the LCS of strings $x,y$ has length at least $L$, we obtain a sketch size and streaming space usage of $\mathcal{O}(L^{|\Sigma| - 1} \log L)$. We also prove matching unconditional lower bounds. As an application, we study a variant of LCS where each alphabet symbol is equipped with a weight that is given as input, and the task is to compute a common subsequence of maximum total weight. Using our sketching algorithm, we obtain an $\mathcal{O}(\textrm{min}\{nm, n + m^{{\lvert \Sigma \rvert}}\})$-time algorithm for this problem, on strings $x,y$ of length $n,m$, with $n \ge m$. We prove optimality of this running time up to lower order factors, assuming the Strong Exponential Time Hypothesis., Comment: To appear in FSTTCS 2018

In the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $P'$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $P'$ are as close as possible. Closeness is usually measured using the Hausdorff or Fr\'echet distance. These distance measures can be applied "globally", i.e., to the whole curves $P$ and $P'$, or "locally", i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff (known to be NP-hard), Local-Hausdorff (in time $O(n^3)$), Global-Fr\'echet (in time $O(k n^5)$), and Local-Fr\'echet (in time $O(n^3)$). Our contribution is as follows. - Cubic time for all variants: For Global-Fr\'echet we design an algorithm running in time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet) can be solved in cubic time. All these algorithms work over a general metric space such as $(\mathbb{R}^d,L_p)$, but the hidden constant depends on $p$ and (linearly) on $d$. - Cubic conditional lower bound: We provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet). Specifically, improving the cubic time to $O(n^{3-\epsilon} \textrm{poly}(d))$ for polyline simplification over $(\mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p \in [1,\infty), p \ne 2$. In total, in high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fr\'echet, and Global-Fr\'echet, by providing new algorithms and conditional lower bounds., Comment: 26 pages