The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick [SICOMP’01]. Many recent works have attempted to improve these original algorithms using the algebraic tools of fast matrix multiplication. We improve on these results for the following problems.

Given two polygons of complexities \(n\) and \(m\) respectively, a fundamental problem in shape matching and geometric similarity is to compute their maximum area overlap under translation. For general simple polygons, the best-known algorithm runs in \(\mathcal{O}((nm)^2 \log(nm))\) time [Mount, Silverman, Wu ’96]. In a recent breakthrough that received the SoCG Best Paper Award 2025, Chan and Hair gave a linear-time algorithm for the special case when both polygons are convex. A key challenge in computational geometry is to design improved algorithms for other natural classes of polygons. We address this by presenting an \(\mathcal{O}((nm)^{3/2} \log(nm))\)-time algorithm for the case when both polygons are orthogonal, probably the most popular class of polygons besides convex and simple ones. This is the first algorithm for polygon overlap on orthogonal polygons that is faster than the almost 30 years old algorithm for general simple polygons.

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

The classic exact pattern matching problem, given two strings——a pattern P of length m and a text T of length n—— asks whether P occurs as a substring of T, that is, $P= T[i. . i+m)$ holds for some $i \in[0. . n-m]$. A property tester for the problem needs to distinguish (with high probability) the following two cases for some threshold $k \in[1. . m)$: the Yes case, where P occurs as a substring of T, and the No case, where $\boldsymbol{P}$ has Hamming distance greater than k from every substring of T, that is, P has no k-mismatch occurrence in T. In this work, we provide adaptive and non-adaptive property testers for the exact pattern matching problem, jointly covering the whole spectrum of parameters. We further establish unconditional lower bounds demonstrating that the time and query complexities of our algorithms are optimal, up to polylog n factors hidden within the $\widetilde{\mathcal{O}}(\cdot)$ notation below. In the most studied regime of $n=m+\Theta(m)$, our nonadaptive property tester has the time complexity of $\widetilde{\mathcal{O}}(n / \sqrt{k})$, and a matching lower bound remains valid for the query complexity of adaptive algorithms. This improves both upon a folklore solution that attains the optimal query complexity but requires $\Omega(n)$ time, and upon the only previously known sublineartime property tester, by Chan, Golan, Kociumaka, Kopelowitz, and Porat [STOC 2020], with time complexity $\widetilde{\mathcal{O}}(n / \sqrt[3]{k})$. The aforementioned results remain valid for $n=m+\Omega(m)$, where our optimal running time $\widetilde{\mathcal{O}}(\sqrt{n m / k}+n / k)$ improves upon the previously best time complexity of $\mathcal{O}\left(\sqrt[3]{n^{2} m / k}+n / k\right)$. In the regime of $n=m+o(m)$, which has not been targeted in any previous work, we establish a surprising separation between adaptive and non-adaptive algorithms, whose optimal time and query complexities are $\widetilde{\mathcal{O}}(\sqrt{(n-m+1) m / k}+n / k)$ and $\widetilde{\mathcal{O}}(\min (n \sqrt{n-m+1} / k, \sqrt{n m / k}+n / k))$, respectively. Our non-adaptive algorithms answer Yes with high probability not only when P has an exact occurrence in T but also when P has an occurrence with at most $k^{\prime}=\Omega(k / \log n)$ mismatches. The gap $k / k^{\prime}$ can be reduced by slightly increasing the running time; an arbitrarily small polynomial overhead already suffices to achieve a constant gap. Moreover, upon request, our algorithms may output a set $A \subseteq[0. . n-m]$ that contains the starting positions of all $\boldsymbol{k}^{\prime}$-mismatch occurrences of $\boldsymbol{P}$ in $\boldsymbol{T}$ and no starting position of an occurrence with more than k mismatches. The key technical innovation behind all our property testers is a novel characterization of the mismatches between the pattern P and the fragments $T[i . . i+m)$ across $i \in[0. . n-m]$. We show that one can select $\widetilde{\mathcal{O}}(k \cdot n / m)$ positions within P and T so that, for every $i \in[0. . n-m]$, at least $\min \left(k, k_{i}\right)$ of the $k_{i}$ mismatches between P and $T[i .. i+m)$ involve a selected position. Previously, such a construction was known for k

We revisit the classic #Knapsack problem, which asks to count the Boolean points (x1, x2, …, xn ) ∈ {0,1}n in a given half-space . This #P-complete problem is known to admit (1 ± ∊)-approximation. Before this work, [Dyer, STOC 2003]’s Õ (n2 5 + n2∊-2)-time randomized approximation scheme remains the fastest known in the natural regime of ε ≥ 1/ poly log n.

We consider the classical k-Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even (2 + ε )-approximation algorithms for every ε > 0 running in near-linear time. The conventional wisdom is that the problem is closed, as (2 — ε )-approximation is NP-hard when k is part of the input, and for constant k ≥ 2 it requires nk-o(1) time under the Strong Exponential Time Hypothesis (SETH).

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.

STOC ’25, Prague, Czechia

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 (also called links) L with weights in {0, 1, . . ., W }, the goal is to choose a minimum weight subset L′ ⊆ L of the links such that G′ = (V, E ∪ L′) is k-edge connected. We give a (2 + ϵ)approximation algorithm for this problem which requires to store O(ϵ−1n log n) words. Moreover, we show the tightness of our result: Any algorithm with better than 2-approximation for the problem requires Ω(n2) 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 + ϵ)-approximate weighted spanner of size at most O(ϵ−1n1+1/t log n) for integer t, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on log W. We believe that this result is of independent interest. Using our spanner result, we provide an optimal O(t)-approximation for k-CAP in the fully streaming model with O(nk + n1+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(kn1+1/t) words of space, where k is the maximum connectivity requirement.

Measuring sequence similarity and compressing texts are among the most fundamental tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the central problems in these two areas: computing the edit distance of two strings [Levenshtein, 1965] and building the Lempel-Ziv factorization of a string [Ziv & Lempel, 1977], respectively.

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.

In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime p∈ [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(logN/Q) rather than O(1/Q); (2) It is difficult to derandomize the choice of p; known derandomization techniques lead to super-logarithmic overhead [Chan, Lewenstein STOC’15].

We study pseudo-polynomial time algorithms for the fundamental 0-1 Knapsack problem. Recent research interest has focused on its fine-grained complexity with respect to the number of items n and the maximum item weight wmax. Under (min,+)-convolution hypothesis, 0-1 Knapsack does not have O((n+wmax)2−δ) time algorithms (Cygan-Mucha-Węgrzycki-Włodarczyk 2017 and K'unnemann-Paturi-Schneider 2017). On the upper bound side, currently the fastest algorithm runs in Õ(n + 12/5) time (Chen, Lian, Mao, and Zhang 2023), improving the earlier O(n + wmax3)-time algorithm by Polak, Rohwedder, and Węgrzycki (2021).

Abstract Our work concerns algorithms for a variant of in unweighted graphs. In the 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). Significant algorithmic breakthroughs have recently shown that over undirected graphs, can be solved in $$n^{2+o(1)}$$ n 2 + o ( 1 ) time, which is essentially optimal. In contrast, the true time complexity of over directed graphs remains open: this problem can be solved in $${\tilde{O}}(m^\omega )$$ O ~ ( m ω ) time, where $$\omega \in [2, 2.373)$$ ω ∈ [ 2 , 2.373 ) is the exponent of matrix multiplication, but no matching conditional lower bound is known. Following [Abboud et al. In: 46th International colloquium on automata, languages, and programming, ICALP 2019, July 9-12, 2019, Patras, Greece, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019], we study a bounded version of $${{\textsf {APC}}}$$ APC called the k- (k- problem. In this variant of , we are given an integer k in addition to the graph G, and are now tasked with reporting the size of a minimum (s, t)-cut only for pairs (s, t) of vertices with min-cut value less than k (if the minimum (s, t)-cut has size at least k, we can just report it is “large” instead of computing the exact value). Our main result is an $${\tilde{O}}((kn)^\omega )$$ O ~ ( ( k n ) ω ) time algorithm solving k- in directed graphs. This is the first algorithm which solves k- faster than simply solving the more general problem exactly, for all $$k\ge 3$$ k ≥ 3 . This runtime is $${{\tilde{O}}}(n^\omega )$$ O ~ ( n ω ) for all $$k\le {{\,\textrm{poly}\,}}(\log n)$$ k ≤ poly ( log n ) , which essentially matches the optimal runtime for the $$k=1$$ k = 1 case of k-, under popular conjectures from fine-grained complexity. Previously, this runtime was only achieved for $$k\le 2$$ k ≤ 2 in general directed graphs [Georgiadis et al. In: 44th international colloquium on automata, languages, and programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017], and for $$k\le o(\sqrt{\log n})$$ k ≤ o ( log n ) in the special case of directed acyclic graphs [Abboud et al. In: 46th international colloquium on automata, languages, and programming, ICALP 2019, July 9–12, 2019, Patras, Greece, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019]. Our result employs the same algebraic framework used in previous work, introduced by [Cheung et al. In: FOCS, 2011]. A direct implementation of this framework involves inverting a large random matrix. Our new algorithm is based off the insight that for solving k-, it suffices to invert a low-rank random matrix instead of a generic random matrix. We also obtain a new algorithm for a variant of k-, the k- (k-) problem, where we are now tasked with reporting, for every pair of vertices (s, t), the maximum number of internally vertex-disjoint (rather than edge-disjoint) paths from

Longest common substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decision 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 \(\widetilde{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 \(\widetilde{O}(\tau^{1/2+o(1)})\) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. 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 et al. (FOCS 2020), we obtain: — \(k\) -mismatch matching has a quantum algorithm with \(k^{3/4}n^{1/2+o(1)}\) query complexity and \(\widetilde{O}(kn^{1/2})\) time complexity. We also observe a non-matching quantum query lower bound of \(\Omega(\sqrt{kn})\) .

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 \ldots 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\left(n \sqrt{m}(\log m \log \log m)^{1 / 4}\right)$ running time. Our randomized algorithm extends to the k-bounded setting, with running time $O\left(n+\frac{n k}{\sqrt{m}}\right)$, removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uznanski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020].•For the $(1+\varepsilon)$-approximate version of Text-to-Pattern Hamming Distances, we give an $\widetilde{O}\left(\varepsilon^{-0.93} n\right)$ time Monte Carlo randomized algorithm (where $\widetilde{O}$ hides poly-logarithmic factors), beating the previous $\widetilde{O}\left(\varepsilon^{-1} n\right)$ running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018].Our approximation algorithm exploits a connection with 3SUM, 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.

Our work concerns algorithms for a variant of Maximum Flow in unweighted graphs. 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). Over undirected graphs, it is known that APC can be solved in essentially optimal n^{2+o(1)} time. In contrast, the true time complexity of APC over directed graphs remains open: this problem can be solved in Õ(m^ω) time, where ω ∈ [2, 2.373) is the exponent of matrix multiplication, but no matching conditional lower bound is known. Following [Abboud et al., ICALP 2019], we study a bounded version of APC called the k-Bounded All Pairs Connectivity (k-APC) problem. In this variant of APC, we are given an integer k in addition to the graph G, and are now tasked with reporting the size of a minimum (s,t)-cut only for pairs (s,t) of vertices with min-cut value less than k (if the minimum (s,t)-cut has size at least k, we can just report it is "large" instead of computing the exact value). Our main result is an Õ((kn)^ω) time algorithm solving k-APC in directed graphs. This is the first algorithm which solves k-APC faster than simply solving the more general APC problem exactly, for all k ≥ 3. This runtime is Õ(n^ω) for all k ≤ poly(log n), which essentially matches the optimal runtime for the k = 1 case of k-APC, under popular conjectures from fine-grained complexity. Previously, this runtime was only achieved for general directed graphs when k ≤ 2 [Georgiadis et al., ICALP 2017]. Our result employs the same algebraic framework used in previous work, introduced by [Cheung, Lau, and Leung, FOCS 2011]. A direct implementation of this framework involves inverting a large random matrix. Our new algorithm is based off the insight that for solving k-APC, it suffices to invert a low-rank random matrix instead of a generic random matrix. We also obtain a new algorithm for a variant of k-APC, the k-Bounded All-Pairs Vertex Connectivity (k-APVC) problem, where for every pair of vertices (s,t), we are now tasked with reporting the maximum number of internally vertex-disjoint (rather than edge-disjoint) paths from s to t if this number is less than k, and otherwise reporting that this number is at least k. Our second result is an Õ(k²n^ω) time algorithm solving k-APVC in directed graphs. Previous work showed how to solve an easier version of the k-APVC problem (where answers only need to be returned for pairs of vertices (s,t) which are not edges in the graph) in Õ((kn)^ω) time [Abboud et al, ICALP 2019]. In comparison, our algorithm solves the full k-APVC problem, and is faster if ω > 2.

Knapsack and Partition are two important additive problems whose fine-grained complexities in the (1 — ε)-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms.

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 ≪ d ≪ n was not fully understood.

Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size-n integer set that avoids solutions to a+b=c+d for {a, b} ≠ {c, d} still requires n2−o(1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics.

Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time $$\tilde{O}(n)$$ O~(n) . Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time (that is, there is a proof system with proofs of length $$\tilde{O}(n^{1.5})$$ O~(n1.5) and a deterministic verifier running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time). Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time $${\tilde{O}}(n^{\lceil k/2\rceil })$$ O~(n⌈k/2⌉) (where $$k\ge 3$$ k≥3 ). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time $${\tilde{O}}(m)$$ O~(m) . Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk. Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time $$\tilde{O}(n^2)$$ O~(n2) . Note this is optimal, as the matrix can have $$\Omega (n^2)$$ Ω(n2) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an $$\tilde{O}(n^{2.94})$$ O~(n2.94) nondeterministic time algorithm. Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time $$2^{n/2 - n/O(k)}$$ 2n/2-n/O(k) . We also observe an algebrization barrier for the previous $$2^{n/2}\cdot \textrm{poly}(n)$$ 2n/2·poly(n) -time Merlin–Arthur protocol of R. Williams [CCC’16] for $$\#$$ # SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in $$2^{n/2}/n^{\omega (1)}$$ 2n/2/nω(1) time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol. Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time $$2^{4n/5}\cdot \textrm{poly}(n)$$ 24n/5·poly(n) . Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in $$2^{2n/3}\cdot \textrm{poly}(n)$$ 22n/3·poly(n) time. Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time $$2^{n/3}\cdot \textrm{poly}(n)$$ 2n/3·poly(n)

Abstract 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})$$ O ~ ( n 2 / 3 ) time, improving upon the recent $$\tilde{O}(n^{5/6})$$ O ~ ( n 5 / 6 ) -time algorithm by Le Gall and Seddighin (in: Proceedings of the 13th innovations in theoretical computer science conference (ITCS 2022), pp 97:1–97:23, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.97 ). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (STOC 2019), ACM, pp 756–767, 2019. https://doi.org/10.1145/3313276.3316368 ) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in $$n^{1/2 + o(1)}$$ n 1 / 2 + o ( 1 ) time, improving upon the recent $$\tilde{O}(n^{3/4})$$ O ~ ( n 3 / 4 ) -time algorithm by Wang and Ying (in: Quantum algorithm for lexicographically minimal string rotation. CoRR, 2020. arXiv:2012.09376 ). 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})$$ O ~ ( n ) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2022) 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.

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$\geq$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)-\varepsilon})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014).Our algorithms use a surprisingly wide range of techniques, including techniques from the girth problem, distance oracles, approximate APSP, spanners, fault-tolerant spanners, and link-cut trees.A highlight of our algorithmic results is that one can solve both n-PSP and ANSC in $O(m+n^{3/2+\in})$ time1with approximation factor $2+\varepsilon$ (and additive error that is function of $\varepsilon$), for any constant $\varepsilon\lt 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.1$\tilde{O}$ hides sub-polynomial factors.Additionally, for ANSC, for all integers $k\geq 1$, we extend the very recent almost k-approximation algorithm for the girth problem that works in $\tilde{O}(n^{1+1/k})$ time [Kadria et al. SODA’22], and obtain an almost k-approximation algorithm for ANSC in $\tilde{O}(mn^{1/k})$ time.

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 Õ(n2/3) time, improving upon the recent Õ(n5/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 n1/2 + o(1) time, improving upon the recent Õ(n3/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 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.

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 Õ(n1.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 Õ(n1.5)-time randomized algorithm using O(log3 n log log n) bits of space, with one-way access to random bits. As a corollary, we also obtain a poly(n)-space O∗(20.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.

Popular fine-grained hypotheses have been successful in proving conditional lower bounds for many dynamic problems. Two of the most widely applicable hypotheses in this context are the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis. The main theme of this paper is using k-dimensional generalizations of these two hypotheses to prove new tight conditional lower bounds for dynamic problems.

For a complexity class C and language L, a constructive separation of “L is not in 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. For many separations, making them constructive would imply breakthrough lower bounds. 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 break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions$\mathbf{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. We also show that under plausible conjectures, there are languages in NP -$\mathbf{P}$for which there are no constructive separations from any complexity class.

Tree edit distance is a well-studied measure of dissimilarity between rooted trees with node labels. It can be computed in O(n³) 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³) time [Touzet, CPM 2005], which improves upon the cubic-time algorithm for k≪ n^{2/3}. In this paper, we give a faster algorithm taking O(nk² log n) time, improving both of the previous results for almost the full range of log n ≪ k≪ n/√{log n}.

We consider the canonical Subset Sum problem: given a list of positive integers a1, …, an and a target integer t with t > ai for all i, determine if there is an S ⊆ [n] such that Σi∊S ai = t. The well-known pseudopolynomialtime dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Ω(t) space. In this paper we present algorithms for Subset Sum with Õ(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 Õ(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 Õ(nt1+∊)-time, Õ(n log t)-space algorithm of Bringmann (SODA 2017). We also give a Õ(n1+∊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 poly log(nt)-space, Õ(n2t)-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter 1 ≤ k ≤ min{n, t}, we present a randomized algorithm running in Õ((n+t) · k) time and O((t/k) poly log(nt)) space. As an application of our results, we give an Õ(min{n2/∊, n/∊2})-time and poly log(nt)-space algorithm for “weak” ∊-approximations of Subset Sum.

We present a massively parallel algorithm, with near-linear memory per machine, that computes a (2+ε)-approximation of minimum-weight vertex cover in O(log log d) rounds, where d is the average degree of the input graph.

We establish several “sharp threshold” results for computational complexity. For certain tasks, we can prove a resource lower bound of n c for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for n c size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing “n c ” with “n c+ε” in our results, for any ε > 0, would imply a breakthrough n ω(1) lower bound. We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (logn) c -size circuits on length-n truth tables (MCSP[(logn) c ]) does not have n 2−o(1)-size probabilistic formulas. We also prove that an n 2+ε lower bound for MCSP[(logn) c ] (for any ε > 0 and c ≥ 1) would imply major lower bound results, such as NP does not have n k -size formulas for all k, and #SAT does not have log-depth circuits. Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions). Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas: (a) For all α, ε > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n 2−2α−ε size with at most 2 n α falsifying assignments. (b) If for some α, ε > 0, there is such an algorithm for probabilistic formulas of n 2−α+ε-size and 2 n α unsatisfying assignments, then a full derandomization of NC 1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, NP does not have n k -size formulas, for all k. Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley’s notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1 n ) outputs a list {(x i ,f(x i ))} i ∈ [poly(n)] ⊆ {0,1} n × {0,1}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all ε > 0, there is an explicit obstruction against n 2−ε-size formulas, and prove that there is an explicit obstruction against n 2+ε-size formulas for some ε > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that E does not have 2 o(n)-size formulas, a breakthrough in circuit complexity.

Dynamic programming is a powerful technique that is, unfortunately, often inherently sequential. That is, there exists no unified method to parallelize algorithms that use dynamic programming. In this paper, we attempt to address this issue in the Massively Parallel Computations (MPC) model which is a popular abstraction of MapReduce-like paradigms. Our main result is an algorithmic framework to adapt a large family of dynamic programs defined over trees. We introduce two classes of graph problems that admit dynamic programming solutions on trees. We refer to them as "(polylog)-expressible" and "linear-expressible" problems. We show that both classes can be parallelized in $O(\log n)$ rounds using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in $O(\log n)$ rounds of MPC, the dynamic programming solution of graph problems such as minimum bisection, $k$-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n1+ε-style) lower bounds for MCSP[2o(m)] or MKtP[2o(m)] would imply breakthrough circuit lower bounds such as NP⊄P/poly, NP⊄NC1, or EXP⊄P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2Õ(s(m))yes-instances of length n = 2m, so MCSP[2o(m)] is 2no(1)-sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an ε > 0 and a language L ∈ NP which is 2no(1)-sparse, and L ∈/ Circuit[n1+ε]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B2-formulas, branching programs, AC0[6] and TC0circuits, and more: improving the state of the art in NP lower bounds against any of these models by an ε factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n1+εcircuit size lower bound for L: one only has to prove a lower bound against n1+ε-time nε-space deterministic algorithms with nεadvice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as ⊕P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC1, AC0[6], or branching programs of polynomial size). For instance, if there is an ε > 0 such that search-MCSP[2βm] does not have De Morgan formulas of size n3+εfor all constants ß > 0, then ⊕P⊄NC1.

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 + ω}{2}}) = \tilde{O}(n^{2.686})$. Here $n$ is the number of vertices, and $ω< 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 - ω}{ω+ 1} + ω)}) = \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+epsilon runs in O~(n + (1/epsilon)^{12/5}) time, where O~ hides polylogarithmic factors. In this paper we present an improved algorithm in O~(n+(1/epsilon)^{9/4}) time, with only a (1/epsilon)^{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.

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 $Ω(n\sqrt{t})$-bit space lower bound, and give a near-optimal algorithm using $O(n\sqrt{t})$ words of space with $2^{-Ω(\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.

Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = +∞) with ties to additive combinatorics and cryptography. Recently, in [Bri17, KX17], efficient algorithms have been developed for the non-modular case, running in near-linear pseudo-polynomial time. For the modular case, however, the best known algorithm by Koiliaris and Xu [KX17] runs in time Õ(m5/4). In this paper, we present an algorithm running in Õ(m) randomized time, which matches a recent conditional lower bound of [ABHS17] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the “textbook” Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for exact combinatorial problems in an offline setting.