CS Paper Radar

Beating Rytter's Bound: All-Pairs CFL Reachability in $O(n^3(\log\log n)^2/(\log n)^2)$ Time

Rupak Majumdar

cs.PL cs.FL ·submitted 2026-11-09 12:40 UTC · v1

Abstract

Context-free reachability and 2NPDA recognition are fundamental problems in program analysis and language theory. Despite years of effort, the best algorithms for these problems run in time $O(n^3/\log n)$ on a word RAM model; they are based on an observation of Rytter in 1985 for 2NPDA which was adapted for CFL reachability by Chaudhuri in 2008. No better algorithm has been designed since. We give the first improvement to Rytter's algorithm. For both all-pairs context-free reachability and 2NPDA recognition, we show a deterministic algorithm running in $O(n^3(\log\log n)^2/(\log n)^2)$ time and $O(n^{2+ε})$ words of space for every fixed $0<ε<1$ on a word RAM. Our improvement is based on a new data structure that reports set differences using batched maintenance of exact intersection counts, allowing saturation to skip regions that contain no new reachability information.

Comment
25 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.63
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

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.61
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

Quadratic-Time Barriers from Self-Referential SAT

cs.DS ·2026-11-05 ·Guangyan Zhou
similarity 0.60
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.

0.21

Tokenization: Hardness and Bicriteria Approximation Algorithms

cs.DS cs.AIcs.CC ·2026-11-11 ·Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
theory similarity 0.59
Abstract

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

0.18

Deterministic Linear-Time Modular Subset Sum

cs.DS ·2026-09-25 ·Phuoc Dinh Le, Kha Le
theory similarity 0.59
Abstract · 13 pages, 4 figures

We give a deterministic $O(m)$-time algorithm for exact modular subset sum over every modulus $m$. The input gives distinct residues and their multiplicities. The algorithm reports all reachable residues and answers one target query. It returns a witness when the target is reachable. The algorithm uses $O(m)$ auxiliary words on an arithmetic word-RAM. This improves Potępa's deterministic $O(m\log m\,α(m))$-time bound under the same input convention. The running time matches the cost of returning a length-$m$ Boolean array. We represent reachable residues as runs along cycles of repeated addition. Newly reached residues pay for scans of partial runs. Packed cycle flags make rebuilding take linear total time at the original modulus. A theorem on subset sums of distinct units limits the number of adaptive boundary batches to $O(m^{3/4})$. Radix sorting their $O(m)$ total keys also takes $O(m)$ time.

0.28

Fine-Grained Hardness of Approximating Dynamic Time Warping

cs.CC cs.DS ·2026-10-06 ·Jihan Wang
theory similarity 0.58
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

On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression

cs.IT ·2026-10-19 ·Pierre-Fran{\c c}ois Marteau
theory similarity 0.58
Abstract

We introduce and study the adaptive covering complexity C adapt S (s), defined as the minimum number of contiguous factor blocks required to partition a string s when each block is either a factor of a fixed external dictionary S or a factor of the target's already decoded prefix. This hybrid admissibility model formalizes the structural interaction between static dictionary matching and dynamic nonoverlapping self-referencing. Our main theoretical result is the exact logarithmic law which is tight and proves that dynamic self-reference can reduce phrase count by at most an exponential factor over static dictionary covering alone. We establish structural equivalences showing that the measure bridges word-segmented Relative Lempel-Ziv and non-overlapping LZ77, and we prove exact preset-history LZ77 sandwich bounds. Furthermore, we establish the optimality of the longest-match greedy parse via an exchange lemma and present an optimal implementation based on dual suffix automata running in O(M + n) time and space for a constant alphabet. These analytical results are complemented by counting bounds, stationary-ergodic asymptotic invariance, a dictionaryselection NP-hardness result, and a concise empirical illustration.

0.16

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.58
Abstract

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

0.53