Search

We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_1,\dots,x_n)\in\{0,1\}^n$ in a given half-space $\sum_{i=1}^nW_ix_i\le T$. This #P-complete problem admits $(1\pm\epsilon)$-approximation. Before this work, [Dyer, STOC 2003]'s $\tilde{O}(n^{2.5}+n^2{\epsilon^{-2}})$-time randomized approximation scheme remains the fastest known in the natural regime of $\epsilon\ge 1/polylog(n)$. In this paper, we give a randomized $(1\pm\epsilon)$-approximation algorithm in $\tilde{O}(n^{1.5}{\epsilon^{-2}})$ time (in the standard word-RAM model), achieving the first sub-quadratic dependence on $n$. Such sub-quadratic running time is rare in the approximate counting literature in general, as a large class of algorithms naturally faces a quadratic-time barrier. Our algorithm follows Dyer's framework, which reduces #Knapsack to the task of sampling (and approximately counting) solutions in a randomly rounded instance with poly(n)-bounded integer weights. We refine Dyer's framework using the following ideas: - We decrease the sample complexity of Dyer's Monte Carlo method, by proving some structural lemmas for typical points near the input hyperplane via hitting-set arguments, and appropriately setting the rounding scale. - Instead of running a vanilla dynamic program on the rounded instance, we employ techniques from the growing field of pseudopolynomial-time Subset Sum algorithms, such as FFT, divide-and-conquer, and balls-into-bins hashing of [Bringmann, SODA 2017]. We also need other ingredients, including a surprising application of the recent Bounded Monotone (max,+)-Convolution algorithm by [Chi-Duan-Xie-Zhang, STOC 2022] (adapted by [Bringmann-D\"urr-Polak, ESA 2024]), the notion of sum-approximation from [Gawrychowski-Markin-Weimann, ICALP 2018]'s #Knapsack approximation scheme, and a two-phase extension of Dyer's framework for handling tiny weights., Comment: To appear at SODA 2025

The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before -- and as we will demonstrate again -- insights on 3SUM can also lead to algorithmic applications. The starting point of our work is that we spend a lot of technical effort to develop new algorithms for 3SUM-type problems such as approximate 3SUM-counting, small-doubling 3SUM-counting, and a deterministic subquadratic-time algorithm for the celebrated Balog-Szemer\'edi-Gowers theorem from additive combinatorics. As consequences of these tools, we derive diverse new results in fine-grained complexity and pattern matching algorithms, answering open questions from many unrelated research areas. Specifically: - A recent line of research on the "short cycle removal" technique culminated in tight 3SUM-based lower bounds for various graph problems via randomized fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC '23]. In this paper we derandomize the reduction to the important 4-Cycle Listing problem. - We establish that \#3SUM and 3SUM are fine-grained equivalent under deterministic reductions. - We give a deterministic algorithm for the $(1+\epsilon)$-approximate Text-to-Pattern Hamming Distances problem in time $n^{1+o(1)} \cdot \epsilon^{-1}$. - In the $k$-Mismatch Constellation problem the input consists of two integer sets $A, B \subseteq [N]$, and the goal is to test whether there is a shift $c$ such that $|(c + B) \setminus A| \leq k$ (i.e., whether $B$ shifted by $c$ matches $A$ up to $k$ mismatches). For moderately small $k$ the previously best running time was $\tilde O(|A| \cdot k)$ [Cardoze, Schulman; FOCS '98] [Fischer; SODA '24]. We give a faster $|A| \cdot k^{2/3} \cdot N^{o(1)}$-time algorithm in the regime where $|B| = \Theta(|A|)$., Comment: To appear in SODA 2025. Abstract shortened to fit arXiv requirements

In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime $p\in [Q/2,Q]$ for some parameter $Q$, which reduces the range of the input integers while preserving their additive structure. However, this hash family suffers from two drawbacks, which led to bottlenecks in many state-of-the-art algorithms: (1) The collision probability of two elements from $[N]$ is $O(\frac{\log N}{Q})$ rather than $O(\frac{1}{Q})$; (2) It is difficult to derandomize the choice of $p$; known derandomization techniques lead to super-logarithmic overhead [Chan, Lewenstein STOC'15]. In this paper, we partially overcome these drawbacks in certain scenarios, via novel applications of the large sieve inequality from analytic number theory. Consequently, we obtain the following improved algorithms for various problems (in the standard word RAM model): Sparse Nonnegative Convolution: We obtain an $O(t\log t)$-time Las Vegas algorithm that computes the convolution $A\star B$ of two nonnegative integer vectors $A,B$, where $t$ is the output sparsity $\|A\star B\|_0$. Moreover, our algorithm terminates in $O(t\log t)$ time with $1-1/\mathrm{poly}(t)$ probability. Text-to-Pattern Hamming Distances: Given a length-$m$ pattern $P$ and a length-$n$ text $T$, we obtain a deterministic $O(n\sqrt{m\log \log m})$-time algorithm that exactly computes the Hamming distance between $P$ and every length-$m$ substring of $T$. Sparse General Convolution: We also give a Monte Carlo $O(t\log t)$ time algorithm for sparse convolution with possibly negative input in the restricted case where the length $N$ of the input vectors satisfies $N\le t^{1.99}$., Comment: To appear at STOC 2024

An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search problem proposed by Papadimitriou (1994): given $n$ positive integers $w_1,\dots,w_n$ of total sum $\sum_{i=1}^n w_i < 2^n-1$, the task is to find two distinct subsets $A, B \subseteq [n]$ such that $\sum_{i\in A}w_i=\sum_{i\in B}w_i$. Similar to the status of the Subset Sum problem, the best known algorithm for Pigeonhole Equal Sums runs in $O^*(2^{n/2})$ time, via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelh\"{o}fer, and Santha, 2022). Our main result is an improved algorithm for Pigeonhole Equal Sums in $O^*(2^{0.4n})$ time. We also give a polynomial-space algorithm in $O^*(2^{0.75n})$ time. Unlike many previous works in this area, our approach does not use the representation method, but rather exploits a simple structural characterization of input instances with few solutions., Comment: 11 pages

We study the $k$-connectivity augmentation problem ($k$-CAP) in the single-pass streaming model. Given a $(k-1)$-edge connected graph $G=(V,E)$ that is stored in memory, and a stream of weighted edges $L$ with weights in $\{0,1,\dots,W\}$, the goal is to choose a minimum weight subset $L'\subseteq L$ such that $G'=(V,E\cup L')$ is $k$-edge connected. We give a $(2+\epsilon)$-approximation algorithm for this problem which requires to store $O(\epsilon^{-1} n\log n)$ words. Moreover, we show our result is tight: Any algorithm with better than $2$-approximation for the problem requires $\Omega(n^2)$ bits of space even when $k=2$. This establishes a gap between the optimal approximation factor one can obtain in the streaming vs the offline setting for $k$-CAP. We further consider a natural generalization to the fully streaming model where both $E$ and $L$ arrive in the stream in an arbitrary order. We show that this problem has a space lower bound that matches the best possible size of a spanner of the same approximation ratio. Following this, we give improved results for spanners on weighted graphs: We show a streaming algorithm that finds a $(2t-1+\epsilon)$-approximate weighted spanner of size at most $O(\epsilon^{-1} n^{1+1/t}\log n)$ for integer $t$, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on $\log W$. Using our spanner result, we provide an optimal $O(t)$-approximation for $k$-CAP in the fully streaming model with $O(nk + n^{1+1/t})$ words of space. Finally we apply our results to network design problems such as Steiner tree augmentation problem (STAP), $k$-edge connected spanning subgraph ($k$-ECSS), and the general Survivable Network Design problem (SNDP). In particular, we show a single-pass $O(t\log k)$-approximation for SNDP using $O(kn^{1+1/t})$ words of space, where $k$ is the maximum connectivity requirement.

We study scheduling of computation graphs to minimize peak memory consumption, an increasingly critical task due to the surge in popularity of large deep-learning models. This problem corresponds to the weighted version of the classical one-shot black pebbling game. We propose the notion of a dominant schedule to capture the idea of finding the ``best'' schedule for a subgraph and introduce new tools to compute and utilize dominant schedules. Surprisingly, we show that despite the strong requirements, a dominant schedule exists for any computation graph; and, moreover, that it is possible to compute the dominant schedule efficiently whenever we can find optimal schedules efficiently for a particular class of graphs (under mild technical conditions). We apply these new tools to analyze trees and series-parallel graphs. We show that the weighted one-shot black pebbling game is strongly NP-complete even when the graph is an out-tree -- or simpler still, a pumpkin, one of the simplest series-parallel graphs. On the positive side, we design a fixed-parameter tractable algorithm to find a dominant schedule (hence also a peak memory minimizing schedule) for series-parallel graphs when parameterized by the out-degree. This algorithm runs in time $2^{O(d \log d)} \cdot poly(n)$ for series-parallel graphs with $n$ nodes and maximum out-degree $d$; for pumpkins, we can improve the dependence on $d$ to $O(2^d \cdot poly(n))$.

Classically, the edit distance of two length-$n$ strings can be computed in $O(n^2)$ time, whereas an $O(n^{2-\epsilon})$-time procedure would falsify the Orthogonal Vectors Hypothesis. If the edit distance does not exceed $k$, the running time can be improved to $O(n+k^2)$, which is near-optimal (conditioned on OVH) as a function of $n$ and $k$. Our first main contribution is a quantum $\tilde{O}(\sqrt{nk}+k^2)$-time algorithm that uses $\tilde{O}(\sqrt{nk})$ queries, where $\tilde{O}(\cdot)$ hides polylogarithmic factors. This query complexity is unconditionally optimal, and any significant improvement in the time complexity would resolve a long-standing open question of whether edit distance admits an $O(n^{2-\epsilon})$-time quantum algorithm. Our divide-and-conquer quantum algorithm reduces the edit distance problem to a case where the strings have small Lempel-Ziv factorizations. Then, it combines a quantum LZ compression algorithm with a classical edit-distance subroutine for compressed strings. The LZ factorization problem can be classically solved in $O(n)$ time, which is unconditionally optimal in the quantum setting. We can, however, hope for a quantum speedup if we parameterize the complexity in terms of the factorization size $z$. Already a generic oracle identification algorithm yields the optimal query complexity of $\tilde{O}(\sqrt{nz})$ at the price of exponential running time. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $\tilde{O}(\sqrt{nz})$. The key tool is a novel LZ-like factorization of size $O(z\log^2n)$ whose subsequent factors can be efficiently computed through a combination of classical and quantum techniques. We can then obtain the string's run-length encoded Burrows-Wheeler Transform (BWT), construct the $r$-index, and solve many fundamental string processing problems in time $\tilde{O}(\sqrt{nz})$., Comment: Accepted to SODA 2024. arXiv admin note: substantial text overlap with arXiv:2302.07235

Roundtrip spanners are the analog of spanners in directed graphs, where the roundtrip metric is used as a notion of distance. Recent works have shown existential results of roundtrip spanners nearly matching the undirected case, but the time complexity for constructing roundtrip spanners is still widely open. This paper focuses on developing fast algorithms for roundtrip spanners and related problems. For any $n$-vertex directed graph $G$ with $m$ edges (with non-negative edge weights), our results are as follows: - 3-roundtrip spanner faster than APSP: We give an $\tilde{O}(m\sqrt{n})$-time algorithm that constructs a roundtrip spanner of stretch $3$ and optimal size $O(n^{3/2})$. Previous constructions of roundtrip spanners of the same size either required $\Omega(nm)$ time [Roditty, Thorup, Zwick SODA'02; Cen, Duan, Gu ICALP'20], or had worse stretch $4$ [Chechik and Lifshitz SODA'21]. - Optimal roundtrip emulator in dense graphs: For integer $k\ge 3$, we give an $O(kn^2\log n)$-time algorithm that constructs a roundtrip \emph{emulator} of stretch $(2k-1)$ and size $O(kn^{1+1/k})$, which is optimal for constant $k$ under Erd\H{o}s' girth conjecture. Previous work of [Thorup and Zwick STOC'01] implied a roundtrip emulator of the same size and stretch, but it required $\Omega(nm)$ construction time. Our improved running time is near-optimal for dense graphs. - Faster girth approximation in sparse graphs: We give an $\tilde{O}(mn^{1/3})$-time algorithm that $4$-approximates the girth of a directed graph. This can be compared with the previous $2$-approximation algorithm in $\tilde{O}(n^2, m\sqrt{n})$ time by [Chechik and Lifshitz SODA'21]. In sparse graphs, our algorithm achieves better running time at the cost of a larger approximation ratio., Comment: To appear in SODA 2024

Listing copies of small subgraphs (such as triangles, $4$-cycles, small cliques) in the input graph is an important and well-studied problem in algorithmic graph theory. In this paper, we give a simple algorithm that lists $t$ (non-induced) $6$-cycles in an $n$-node undirected graph in $\tilde O(n^2+t)$ time. This nearly matches the fastest known algorithm for detecting a $6$-cycle in $O(n^2)$ time by Yuster and Zwick (1997). Previously, a folklore $O(n^2+t)$-time algorithm was known for the task of listing $4$-cycles., Comment: 10 pages; SOSA 2024

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift $i$, under the standard Word-RAM model with $\Theta(\log n)$-bit words. - We provide an $O(n\sqrt{m})$ time Las Vegas randomized algorithm for this problem, beating the decades-old $O(n \sqrt{m \log m})$ running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher $O(n\sqrt{m}(\log m\log\log m)^{1/4})$ running time. Our randomized algorithm extends to the $k$-bounded setting, with running time $O\big(n+\frac{nk}{\sqrt{m}}\big)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uzna\'{n}ski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the $(1+\epsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\tilde{O}(\epsilon^{-0.93}n)$ time Monte Carlo randomized algorithm, beating the previous $\tilde{O}(\epsilon^{-1}n)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with $3$SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of $3$SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of $3$SUM., Comment: Appeared in FOCS 2023. Abstract shortened to fit arXiv requirements. v2: added reference and discussion related to Lemma 2.2 and Appendix B

We study pseudo-polynomial time algorithms for the fundamental \emph{0-1 Knapsack} problem. Recent research interest has focused on its fine-grained complexity with respect to the number of items $n$ and the \emph{maximum item weight} $w_{\max}$. Under $(\min,+)$-convolution hypothesis, 0-1 Knapsack does not have $O((n+w_{\max})^{2-\delta})$ time algorithms (Cygan-Mucha-W\k{e}grzycki-W\l{}odarczyk 2017 and K\"{u}nnemann-Paturi-Schneider 2017). On the upper bound side, currently the fastest algorithm runs in $\tilde O(n + w_{\max}^{12/5})$ time (Chen, Lian, Mao, and Zhang 2023), improving the earlier $O(n + w_{\max}^3)$-time algorithm by Polak, Rohwedder, and W\k{e}grzycki (2021). In this paper, we close this gap between the upper bound and the conditional lower bound (up to subpolynomial factors): - The 0-1 Knapsack problem has a deterministic algorithm in $O(n + w_{\max}^{2}\log^4w_{\max})$ time. Our algorithm combines and extends several recent structural results and algorithmic techniques from the literature on knapsack-type problems: - We generalize the "fine-grained proximity" technique of Chen, Lian, Mao, and Zhang (2023) derived from the additive-combinatorial results of Bringmann and Wellnitz (2021) on dense subset sums. This allows us to bound the support size of the useful partial solutions in the dynamic program. - To exploit the small support size, our main technical component is a vast extension of the "witness propagation" method, originally designed by Deng, Mao, and Zhong (2023) for speeding up dynamic programming in the easier unbounded knapsack settings. To extend this approach to our 0-1 setting, we use a novel pruning method, as well as the two-level color-coding of Bringmann (2017) and the SMAWK algorithm on tall matrices., Comment: v2 comment: To appear in STOC 2024. v1 comment: This paper supersedes an earlier manuscript arXiv:2307.09454 that contained weaker results. Content from the earlier manuscript is partly incorporated into this paper. The earlier manuscript is now obsolete

We study pseudo-polynomial time algorithms for the fundamental \emph{0-1 Knapsack} problem. In terms of $n$ and $w_{\max}$, previous algorithms for 0-1 Knapsack have cubic time complexities: $O(n^2w_{\max})$ (Bellman 1957), $O(nw_{\max}^2)$ (Kellerer and Pferschy 2004), and $O(n + w_{\max}^3)$ (Polak, Rohwedder, and W\k{e}grzycki 2021). On the other hand, fine-grained complexity only rules out $O((n+w_{\max})^{2-\delta})$ running time, and it is an important question in this area whether $\tilde O(n+w_{\max}^2)$ time is achievable. Our main result makes significant progress towards solving this question: - The 0-1 Knapsack problem has a deterministic algorithm in $\tilde O(n + w_{\max}^{2.5})$ time. Our techniques also apply to the easier \emph{Subset Sum} problem: - The Subset Sum problem has a randomized algorithm in $\tilde O(n + w_{\max}^{1.5})$ time. This improves (and simplifies) the previous $\tilde O(n + w_{\max}^{5/3})$-time algorithm by Polak, Rohwedder, and W\k{e}grzycki (2021) (based on Galil and Margalit (1991), and Bringmann and Wellnitz (2021)). Similar to recent works on Knapsack (and integer programs in general), our algorithms also utilize the \emph{proximity} between optimal integral solutions and fractional solutions. Our new ideas are as follows: - Previous works used an $O(w_{\max})$ proximity bound in the $\ell_1$-norm. As our main conceptual contribution, we use an additive-combinatorial theorem by Erd\H{o}s and S\'{a}rk\"{o}zy (1990) to derive an $\ell_0$-proximity bound of $\tilde O(\sqrt{w_{\max}})$. - Then, the main technical component of our Knapsack result is a dynamic programming algorithm that exploits both $\ell_0$- and $\ell_1$-proximity. It is based on a vast extension of the ``witness propagation'' method, originally designed by Deng, Mao, and Zhong (2023) for the easier \emph{unbounded} setting only., Comment: This manuscript is superseded by an updated version arXiv:2308.04093. See Section 1.1

Our work concerns algorithms for an unweighted variant of Maximum Flow. In the All-Pairs Connectivity (APC) problem, we are given a graph $G$ on $n$ vertices and $m$ edges, and are tasked with computing the maximum number of edge-disjoint paths from $s$ to $t$ (equivalently, the size of a minimum $(s,t)$-cut) in $G$, for all pairs of vertices $(s,t)$. Although over undirected graphs APC can be solved in essentially optimal $n^{2+o(1)}$ time, the true time complexity of APC over directed graphs remains open: this problem can be solved in $\tilde{O}(m^\omega)$ time, where $\omega \in [2, 2.373)$ is the exponent of matrix multiplication, but no matching conditional lower bound is known. We study a variant of APC called the $k$-Bounded All Pairs Connectivity ($k$-APC) problem. In this problem, we are given an integer $k$ and graph $G$, and are tasked with reporting the size of a minimum $(s,t)$-cut only for pairs $(s,t)$ of vertices with a minimum cut size less than $k$ (if the minimum $(s,t)$-cut has size at least $k$, we just report it is "large" instead of computing the exact value). We present an algorithm solving $k$-APC in directed graphs in $\tilde{O}((kn)^\omega)$ time. This runtime is $\tilde O(n^\omega)$ for all $k$ polylogarithmic in $n$, which is essentially optimal under popular conjectures from fine-grained complexity. Previously, this runtime was only known for $k\le 2$ [Georgiadis et al., ICALP 2017]. We also study a variant of $k$-APC, the $k$-Bounded All-Pairs Vertex Connectivity ($k$-APVC) problem, which considers internally vertex-disjoint paths instead of edge-disjoint paths. We present an algorithm solving $k$-APVC in directed graphs in $\tilde{O}(k^2n^\omega)$ time. Previous work solved an easier version of the $k$-APVC problem in $\tilde O((kn)^\omega)$ time [Abboud et al, ICALP 2019].

Knapsack and Partition are two important additive problems whose fine-grained complexities in the $(1-\varepsilon)$-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms. - Knapsack can be $(1 - \varepsilon)$-approximated in $\tilde O(n + (1/\varepsilon) ^ {2.2} )$ time, improving the previous $\tilde O(n + (1/\varepsilon) ^ {2.25} )$ by Jin (ICALP'19). There is a known conditional lower bound of $(n+\varepsilon)^{2-o(1)}$ based on $(\min,+)$-convolution hypothesis. - Partition can be $(1 - \varepsilon)$-approximated in $\tilde O(n + (1/\varepsilon) ^ {1.25} )$ time, improving the previous $\tilde O(n + (1/\varepsilon) ^ {1.5} )$ by Bringmann and Nakos (SODA'21). There is a known conditional lower bound of $(1/\varepsilon)^{1-o(1)}$ based on Strong Exponential Time Hypothesis. Both of our new algorithms apply the additive combinatorial results on dense subset sums by Galil and Margalit (SICOMP'91), Bringmann and Wellnitz (SODA'21). Such techniques have not been explored in the context of Knapsack prior to our work. In addition, we design several new methods to speed up the divide-and-conquer steps which naturally arise in solving additive problems., Comment: To appear in SODA 2023. Corrects minor mistakes in Lemma 3.3 and Lemma 3.5 in the proceedings version of this paper

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold $d$, asks whether two length-$n$ input strings have a common substring of length $d$. The two extreme cases, $d=1$ and $d=n$, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case $1\ll d\ll n$ was not fully understood. We show that the complexity of LCS with threshold $d$ smoothly interpolates between the two extreme cases up to $n^{o(1)}$ factors: LCS with threshold $d$ has a quantum algorithm in $n^{2/3+o(1)}/d^{1/6}$ query complexity and time complexity, and requires at least $\Omega(n^{2/3}/d^{1/6})$ quantum query complexity. Our result improves upon previous upper bounds $\tilde O(\min \{n/d^{1/2}, n^{2/3}\})$ (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples $n/\tau^{1-o(1)}$ synchronizing positions in the string depending on their length-$\Theta(\tau)$ contexts, and each synchronizing position can be reported by a quantum algorithm in $\tilde O(\tau^{1/2+o(1)})$ time. As another application of our quantum string synchronizing set, we study the $k$-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most $k$ Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for $k$-mismatch matching with $k^{3/4} n^{1/2+o(1)}$ query complexity and $\tilde O(kn^{1/2})$ time complexity., Comment: SODA 2023. Abstract shortened to meet arXiv requirements

Our work explores the hardness of $3$SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving $3$SUM on a size-$n$ integer set that avoids solutions to $a+b=c+d$ for $\{a, b\} \ne \{c, d\}$ still requires $n^{2-o(1)}$ time, under the $3$SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics. - Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on $n$-vertex graphs with maximum degree $\sqrt{n}$ and at most $n^{k/2}$ $k$-cycles for every $k \ge 3$ requires $n^{2-o(1)}$ time, under the $3$SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC'22] of $4$-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the $4$-Cycle Enumeration problem on $n$-vertex $m$-edge graphs with $n^{o(1)}$ delays has $O(n^{2-\varepsilon})$ or $O(m^{4/3-\varepsilon})$ pre-processing time for $\varepsilon >0$. We also present a matching upper bound via simple modifications of the known algorithms for $4$-Cycle Detection. - A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC'20] on the $3$SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show $3$SUM hardness for all nontrivial 4-LDTs. The proof of our main technical result combines a wide range of tools: Balog-Szemer{\'e}di-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost $3$-universal guarantee for integers that do not have small-coefficient linear relations.

We study the approximability of two related problems on graphs with $n$ nodes and $m$ edges: $n$-Pairs Shortest Paths ($n$-PSP), where the goal is to find a shortest path between $O(n)$ prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate $n$-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate $n$-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation. We provide a thorough study of the approximability of $n$-PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio. A highlight of our conditional lower bounds results is that for any integer $k\ge 1$, under the combinatorial $4k$-clique hypothesis, there is no combinatorial algorithm for unweighted undirected $n$-PSP with approximation ratio better than $1+1/k$ that runs in $O(m^{2-2/(k+1)}n^{1/(k+1)-\epsilon})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014). A highlight of our algorithmic results is that one can solve both $n$-PSP and ANSC in $\tilde O(m+ n^{3/2+\epsilon})$ time with approximation factor $2+\epsilon$ (and additive error that is function of $\epsilon$), for any constant $\epsilon>0$. For $n$-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for $n$-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms., Comment: Abstract truncated to meet arXiv requirement. To appear in FOCS 2022

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that "constructiveness" serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against $P$, $ZPP$, and $BPP$. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply breakthrough separations ranging from $EXP \neq BPP$ to even $P \neq NP$. 2. Our second set of results shows that for most major open problems in lower bounds against $P$, $ZPP$, and $BPP$, including $P \neq NP$, $P \neq PSPACE$, $P \neq PP$, $ZPP \neq EXP$, and $BPP \neq NEXP$, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for $P \neq NP$ [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and $BPP \neq NEXP$ [Dolev, Fandina and Gutfreund, CIAC 2013]. 3. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions $t$, there are no constructive separations for detecting high $t$-time Kolmogorov complexity (a task which is known to be not in $P$) from any complexity class, unconditionally., Comment: Abstract shortened to fit arXiv requirements

The main theme of this paper is using $k$-dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis to prove new tight conditional lower bounds for dynamic problems. The combinatorial $k$-Clique hypothesis, which is a standard hypothesis in the literature, naturally generalizes the combinatorial BMM hypothesis. In this paper, we prove tight lower bounds for several dynamic problems under the combinatorial $k$-Clique hypothesis. For instance, we show that: * The Dynamic Range Mode problem has no combinatorial algorithms with $\mathrm{poly}(n)$ pre-processing time, $O(n^{2/3-\epsilon})$ update time and $O(n^{2/3-\epsilon})$ query time for any $\epsilon > 0$, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with $O(n^{1/2-\epsilon})$ update and query time under the OMv hypothesis. Other examples include tight combinatorial lower bounds for Dynamic Subgraph Connectivity, Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-Pattern Document Retrieval, and Dynamic Range Mode in higher dimensions. Furthermore, we propose the OuMv$_k$ hypothesis as a natural generalization of the OMv hypothesis. Under this hypothesis, we prove tight lower bounds for various dynamic problems. For instance, we show that: * The Dynamic Skyline Points Counting problem in $(2k-1)$-dimensional space has no algorithm with $\mathrm{poly}(n)$ pre-processing time and $O(n^{1-1/k-\epsilon})$ update and query time for $\epsilon > 0$, even if the updates are semi-online. Other examples include tight conditional lower bounds for (semi-online) Dynamic Klee's measure for unit cubes, and high-dimensional generalizations of Erickson's problem and Langerman's problem., Comment: To appear at STOC'22. Abstract shortened to fit arXiv requirements

We consider low-space algorithms for the classic Element Distinctness problem: given an array of $n$ input integers with $O(\log n)$ bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gave an $\tilde O(n^{1.5})$-time randomized algorithm for Element Distinctness using only $O(\log n)$ bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed. In this paper, we positively answer this question by giving an $\tilde O(n^{1.5})$-time randomized algorithm using $O(\log ^3 n\log \log n)$ bits of space, with one-way access to random bits. As a corollary, we also obtain a $\operatorname{\mathrm{poly}}(n)$-space $O^*(2^{0.86n})$-time randomized algorithm for the Subset Sum problem, removing the random oracles required in the algorithm of Bansal, Garg, Nederlof, and Vyas [STOC 2017]. The main technique underlying our results is a pseudorandom hash family based on iterative restrictions, which can fool the cycle-finding procedure in the algorithms of Beame et al. and Bansal et al., Comment: To appear in SODA 2022

We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: - Longest Common Substring can be solved by a quantum algorithm in $\tilde O(n^{2/3})$ time, improving upon the recent $\tilde O(n^{5/6})$-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. - Lexicographically Minimal String Rotation can be solved by a quantum algorithm in $n^{1/2 + o(1)}$ time, improving upon the recent $\tilde O(n^{3/4})$-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. - Longest Square Substring can be solved by a quantum algorithm in $\tilde O(\sqrt{n})$ time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix., Comment: To appear in SODA 2022. Fixed cleveref issues

Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in $O(n^3)$ time [Demaine, Mozes, Rossman, and Weimann, ICALP 2007], and fine-grained hardness results suggest that the weighted version of this problem cannot be solved in truly subcubic time unless the APSP conjecture is false [Bringmann, Gawrychowski, Mozes, and Weimann, SODA 2018]. We consider the unweighted version of tree edit distance, where every insertion, deletion, or relabeling operation has unit cost. Given a parameter $k$ as an upper bound on the distance, the previous fastest algorithm for this problem runs in $O(nk^3)$ time [Touzet, CPM 2005], which improves upon the cubic-time algorithm for $k\ll n^{2/3}$. In this paper, we give a faster algorithm taking $O(nk^2 \log n)$ time, improving both of the previous results for almost the full range of $\log n \ll k\ll n/\sqrt{\log n}$., Comment: To appear in ICALP 2021. Updated funding information and references

We consider the canonical Subset Sum problem: given a list of positive integers $a_1,\ldots,a_n$ and a target integer $t$ with $t > a_i$ for all $i$, determine if there is an $S \subseteq [n]$ such that $\sum_{i \in S} a_i = t$. The well-known pseudopolynomial-time dynamic programming algorithm [Bellman, 1957] solves Subset Sum in $O(nt)$ time, while requiring $\Omega(t)$ space. In this paper we present algorithms for Subset Sum with $\tilde O(nt)$ running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in $\tilde O(nt)$ time and $O(\log(nt))$ space with access to $O(\log n \log \log n+\log t)$ random bits. This significantly improves upon the $\tilde O(n t^{1+\varepsilon})$-time, $\tilde O(n\log t)$-space algorithm of Bringmann (SODA 2017). We also give an $\tilde O(n^{1+\varepsilon}t)$-time, $O(\log(nt))$-space randomized algorithm, improving upon previous $(nt)^{O(1)}$-time $O(\log(nt))$-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a $\mathrm{poly} \log(nt)$-space, $\tilde O(n^2 t)$-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter $1\le k\le \min\{n,t\}$, we present a randomized algorithm running in $\tilde O((n+t)\cdot k)$ time and $O((t/k) \mathrm{polylog} (nt))$ space. As an application of our results, we give an $\tilde{O}(\min\{n^2/\varepsilon, n/\varepsilon^2\})$-time and $\mathrm{polylog}(nt)$-space algorithm for "weak" $\varepsilon$-approximations of Subset Sum., Comment: To appear in SODA 2021

We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input $x\in\Sigma^n$ and Bob with input $y\in\Sigma^n$, that share public randomness and are given a promise that the edit distance $\mathsf{ed}(x,y)$ between their two strings is at most some given value $k$. Alice must send a message $sx$ and Bob must send $sy$ to a third party Charlie, who does not know the inputs but shares the same public randomness and also knows $k$. Charlie must output $\mathsf{ed}(x,y)$ precisely as well as a sequence of $\mathsf{ed}(x,y)$ edits required to transform $x$ into $y$. The goal is to minimize the lengths $|sx|, |sy|$ of the messages sent. The protocol of Belazzougui and Zhang (FOCS 2016), building upon the random walk method of Chakraborty, Goldenberg, and Kouck\'y (STOC 2016), achieves a maximum message length of $\tilde O(k^8)$ bits, where $\tilde O(\cdot)$ hides $\mathrm{poly}(\log n)$ factors. In this work we build upon Belazzougui and Zhang's protocol and provide an improved analysis demonstrating that a slight modification of their construction achieves a bound of $\tilde O(k^3)$., Comment: Appeared in STACS 2021. Fixed the title to match the conference version

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

We present a massively parallel algorithm, with near-linear memory per machine, that computes a $(2+\varepsilon)$-approximation of minimum-weight vertex cover in $O(\log\log d)$ rounds, where $d$ is the average degree of the input graph. Our result fills the key remaining gap in the state-of-the-art MPC algorithms for vertex cover and matching problems; two classic optimization problems, which are duals of each other. Concretely, a recent line of work---by Czumaj et al. [STOC'18], Ghaffari et al. [PODC'18], Assadi et al. [SODA'19], and Gamlath et al. [PODC'19]---provides $O(\log\log n)$ time algorithms for $(1+\varepsilon)$-approximate maximum weight matching as well as for $(2+\varepsilon)$-approximate minimum cardinality vertex cover. However, the latter algorithm does not work for the general weighted case of vertex cover, for which the best known algorithm remained at $O(\log n)$ time complexity., Comment: To appear in SPAA 2020

We present $O(\log\log n)$ round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded arboricity, as well as for constant coloring trees. Following the standards, by a scalable MPC algorithm, we mean that these algorithms can work on machines that have capacity/memory as small as $n^{\delta}$ for any positive constant $\delta<1$. Our results improve over the $O(\log^2\log n)$ round algorithms of Behnezhad et al. [PODC'19]. Moreover, our matching algorithm is presumably optimal as its bound matches an $\Omega(\log\log n)$ conditional lower bound of Ghaffari, Kuhn, and Uitto [FOCS'19]., Comment: To appear in DISC 2020

In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + \omega}{2}}) = \tilde{O}(n^{2.686})$. Here $n$ is the number of vertices, and $\omega < 2.373$ is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for $(\max, \min)$-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for $(\max, \min)$-matrix product. The previous best upper bound for APNP on weighted digraphs was $\tilde{O}(n^{\frac{1}{2}(3 + \frac{3 - \omega}{\omega + 1} + \omega)}) = \tilde{O}(n^{2.78})$ [Duan, Gu, Zhang 2018]. We also show an $\tilde{O}(n^2)$ time algorithm for APNP in undirected graphs which also reaches optimal within logarithmic factors.

The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approximation factor $1+\varepsilon$ runs in $\tilde O(n + (1/\varepsilon)^{12/5})$ time, where $\tilde O$ hides polylogarithmic factors. In this paper we present an improved algorithm in $\tilde O(n+(1/\varepsilon)^{9/4})$ time, with only a $(1/\varepsilon)^{1/4}$ gap from the quadratic conditional lower bound based on $(\min,+)$-convolution. Our improvement comes from a multi-level extension of Chan's number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items., Comment: To appear at ICALP'19

We study the problem of approximately simulating a $t$-step random walk on a graph where the input edges come from a single-pass stream. The straightforward algorithm using reservoir sampling needs $O(nt)$ words of memory. We show that this space complexity is near-optimal for directed graphs. For undirected graphs, we prove an $\Omega(n\sqrt{t})$-bit space lower bound, and give a near-optimal algorithm using $O(n\sqrt{t})$ words of space with $2^{-\Omega(\sqrt{t})}$ simulation error (defined as the $\ell_1$-distance between the output distribution of the simulation algorithm and the distribution of perfect random walks). We also discuss extending the algorithms to the turnstile model, where both insertion and deletion of edges can appear in the input stream., Comment: To appear in ITCS 2019

Given a multiset $S$ of $n$ positive integers and a target integer $t$, the Subset Sum problem asks to determine whether there exists a subset of $S$ that sums up to $t$. The current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in $\tilde O(\sqrt{n}t)$ time, where $\tilde O$ hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized $\tilde O(n + t)$ time algorithm using two-stage color-coding. The $\tilde O(n+t)$ running time is believed to be near-optimal. In this paper, we present a simple and elegant randomized algorithm for Subset Sum in $\tilde O(n + t)$ time. Our new algorithm actually solves its counting version modulo prime $p>t$, by manipulating generating functions using FFT., Comment: To appear in SOSA 2019 (fixed some typos)