CS Paper Radar

Quadratic-Time Barriers from Self-Referential SAT

Guangyan Zhou

cs.DS ·submitted 2026-11-05 01:50 UTC · v1

Abstract

Under the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in $O(n^{2-η})$ time for any fixed $η>0$, where $n$ is the longer sequence length. The same exclusion holds for one-dimensional dynamic time warping on $\{0,1,2,4,8\}$ with absolute-difference cost and for five-symbol dynamic time warping with the discrete metric. We derive Orthogonal Vectors hardness in polylogarithmic dimension by splitting the variables of the logarithmic-width source formula into two halves. Existing sequence reductions have polynomial overhead in the dimension. Their output lengths and construction times allow a fixed saving in the target exponent to yield a fixed proportional saving in the source exponent.

Closest papers

Nearest neighbours by meaning across the whole index.

Fine-Grained Hardness of Approximating Dynamic Time Warping

cs.CC cs.DS ·2026-10-06 ·Jihan Wang
theory similarity 0.80
Abstract

We prove conditional lower bounds for approximating dynamic time warping (DTW) over the uniform metric on three symbols. Let $N, M$ be the two string lengths and $n, m$ their respective numbers of runs. Under the Gap Block Disjointness (GBD) hypothesis, for every fixed $κ\in (0,1/6)$ and $δ\in (0,1)$, no deterministic algorithm $N^{κδ}$-approximates DTW on two explicit strings of length $N$ in $O(N^{2-δ})$ time. This matches the known tradeoff between approximation and running-time exponents for deterministic algorithms within any fixed factor greater than six in the approximation exponent. For run-length encoded strings, the Orthogonal Vectors Hypothesis (OVH) rules out any constant-factor approximation in $\widetilde{O}((nm)^{1-δ})$ time for every constant $δ>0$. More generally, for every fixed $η\in (0,1)$, it rules out $(N+M)^{1-η}$-approximation in the same running time. These bounds extend to every fixed metric with at least three points, including absolute distance on $\{0,1,2\}$. Both reductions use long runs to force equal-symbol matches in low-cost alignments. For explicit strings, we combine Boolean gadgets with deterministic gap amplification to obtain a polynomial approximation gap. For run-length encoded strings, an encoding of regular-expression membership gives accepting instances an alignment whose cost does not increase as selected runs grow. Rejecting instances have distance at least the chosen run length, while the number of runs stays fixed.

0.13

Dynamic Time Warping in the Low-Distance Regime

cs.DS ·2026-09-30 ·Itai Boneh, Shay Golan, Tomasz Kociumaka
top venuetheory similarity 0.74
Abstract · Accepted to FOCS 2026. Abstract shortened to fit arXiv requirements

Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings $S,T$ over an alphabet $Σ$ and a cost function $δ:Σ^2\to\mathbb{R}_{\ge0}$, $DTW_δ(S,T)$ is the minimum total cost of equal-length expansions of $S$ and $T$ obtained by duplicating characters. For strings of length at most $n$, DTW is computable in $O(n^2)$ time, and this is conditionally optimal under the Orthogonal Vectors Hypothesis (OVH). We study the low-distance regime, where an integer $k$ upper-bounds $DTW_δ(S,T)$, assuming $δ(a,a)=0$ and $δ(a,b)\ge1$ for $a\ne b$. For several classical similarity measures, this regime admits $O(n+\operatorname{poly}(k))$ algorithms, whereas for DTW with metric costs the best known bound is $O(nk)$. We show that this dependence is essentially optimal: assuming OVH, computing DTW requires $n^{1-o(1)}k$ time even for the discrete mismatch-cost function, which assigns cost $1$ to every mismatch. The lower bound applies to the whole spectrum of thresholds $k$ between constant and linear in $n$. Our reduction from Orthogonal Vectors encodes vector coordinates in the lengths of equal-character runs. The resulting instances are very structured: collapsing runs to single characters reveals long substrings with short periods. We complement the lower bound with a $\tilde O(n+\operatorname{poly}(k))$-time algorithm whenever, after collapsing runs in the inputs, every substring with period $O(k)$ has length $\operatorname{poly}(k)$. Finally, we extend this lower bound to DTW pattern matching, which asks whether any non-empty substring of a length-$n$ text has DTW distance at most $k$ from a length-$m$ pattern. We prove that the classic $O(nm)$-time dynamic-programming algorithm is near-optimal under OVH, even when $k=O(\log n)$.

0.58

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.67
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching

cs.DS ·2026-10-09 ·Zemin Chao, Zitong Li, Xiangyu Gao, Hongzhi Wang
theory similarity 0.66
Abstract · 29 pages, 2 tables

We study static indexes for exact subsequence matching over all equal-length windows of a time series. Under deterministic SETH, for every fixed $β\ge1$ and $δ\in(0,1)$, we exclude $O(N^β)$ preprocessing together with $O(N^{1-δ})$ worst-case query time on domains containing the reduction's polylogarithmic query lengths. The bounded-error counterpart assumes randomized SETH. The results cover specified warping, bottleneck, edit, subsequence, local-alignment, and complexity-adjusted scores. Their reductions share a data-independent query interface but require different arguments for all-window soundness. We give complete representative proofs for the distinct mechanisms and state the changes needed by related scores. For soft-DTW, integer scaling yields an exact Boolean-predicate reduction in Word-RAM; a model with exact transcendental primitives requires a separate assumption. For independent window-wise Z-normalization, balanced coordinate gadgets and shifted-window moment bounds yield exact lower bounds for squared-cost DTW and discrete Fréchet distance. We give finite-word comparisons and a specified length-dependent rounding rule preserving these gaps. Raw and normalized discrete Fréchet constructions also exclude feasible-solution approximation within any fixed factor below two. Finally, we prove conditional signal-attenuation bounds for normalized anchor constructions and a fast index under the all-window common-mean promise.

0.29

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.64
Abstract · Revised version with a uniform alphabet-sensitive subexponential algorithm and quantitative transfers to SAT. Source package includes verifi…

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an input of length $n\ge2$ over at most $σ$ symbols, where $2\leσ\le n$, let $R=\log_σn$. We give a deterministic exact algorithm running in $n^{O(1)}2^{O(n\log\log n/(R\sqrt{\log n}))}$ time and polynomial space, with constants independent of $σ$. This gives time $2^{O(n\log\log n/(\log n)^{3/2})}$ for fixed alphabets and $2^{O(n\log\log n/\sqrt{\log n})}$ for arbitrary alphabets, up to polynomial factors. The algorithm combines pairwise disjoint representative occurrences of dictionary strings, a sparse interval certificate, and the Boolean tensor contraction theorem of OpenAI. It explicitly enforces dictionary membership, rule boundaries, and the grammar-size budget. Independently of that contraction theorem, disjoint representatives yield exact algorithms in $O^*(1.872258^n)$ time and $2^{O((n/R)\log(R+1))}$ time using $O(n)$ words of space. Anchor-based grammar projections establish binary NP-completeness and reductions with tunable alphabet size. We state their consequences as unconditional quantitative transfers from SGP algorithms to sparse SAT algorithms, and quantify the additional loss from sparsifying general formulas.

0.45

Fast Geometric Spanners via Approximate Nearest Neighbor Search

cs.DS cs.CG ·2026-09-22 ·Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
similarity 0.62
Abstract

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $Ω(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

0.07

Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes

cs.DS ·2026-10-01 ·Egor Gorbachev
theory similarity 0.61
Abstract · Substantially extended version under a new title, adding the Monge approximation framework and its applications to bounded and dynamic weigh…

The weighted edit distance $\mathsf{ed}^w(X,Y)$ is the minimum cost of an alignment of strings $X$ and $Y$, where a weight function $w$ specifies the cost of each character insertion, deletion, and substitution. For strings of total length $N$, the textbook dynamic program takes $O(N^2)$ time, and no $O(N^{2-δ})$-time algorithm exists, even for unit costs, unless the Orthogonal Vectors Hypothesis (OVH) fails. This motivates the study of approximation algorithms. For unit costs and metric weights, the best truly subquadratic approximation factor was $3+\varepsilon$; we give randomized $3$-approximations in $\tilde O(N^{11/6})$ and $\tilde O(N^{40/21})$ time, respectively. For non-metric weights, we prove quadratic lower bounds for any approximation factor: $Ω(N^2)$ queries to $w$ over alphabets of size $Θ(N)$, and OVH-hardness over constant-size alphabets. These lower bounds motivate the bounded setting, parameterized by $k:=\mathsf{ed}^w(X,Y)$ for $w$ normalized so that every edit costs at least one. We give a deterministic $(1+\varepsilon)$-approximation algorithm in $\tilde O(N+k^2/\sqrt\varepsilon)$ time, matching the $O(N+k^2)$-time Landau-Vishkin algorithm for unit costs up to logarithmic factors for constant $\varepsilon>0$. Our main technical contribution is a Monge-matrix approximation framework for alignment problems: every $n\times n$ Monge matrix with entries in $\{0\}\cup[1,W]$ has an entrywise $(1+\varepsilon)$-approximation by a Monge matrix with $\tilde O(n\log(W)/\sqrt\varepsilon)$ strict Monge inequalities. As further applications of our Monge approximation framework, we maintain a $(1+\varepsilon)$-approximation of $\mathsf{ed}^w(X,Y)$ under character edits in $\tilde O(N\log(W)/\sqrt\varepsilon)$ time per update for weights at most $W$, and in $\tilde O(K/\sqrt\varepsilon)$ time for a fixed threshold $K$.

0.41

Bounded Weighted Edit Distance with Metric Costs

cs.DS ·2026-11-10 ·Jihan Wang
similarity 0.61
Abstract

We give a deterministic $O(n+k^2)$-time algorithm for bounded weighted edit distance when the input costs form an integer metric on the alphabet extended by a gap symbol. Here $n$ is the total input length and $k$ is the given threshold on the distance. If the distance is at most $k$, the algorithm returns it with an optimal alignment. Otherwise, it reports that the distance exceeds $k$. The running time matches the classical unit-cost bound and is independent of the alphabet size and of the largest cost. The algorithm keeps only the farthest-reaching prefix alignment for each cost and each difference between the total gap costs of the aligned prefixes. For real metrics whose nonzero costs are at least one, scaling and upward rounding give a $(1+\varepsilon)$-approximation for the bounded problem in $\widetilde{O}(n+(k/\varepsilon)^2)$ time. If insertions and deletions have integer costs, the running time improves to $\widetilde{O}(n+k^2/\varepsilon)$.

0.20