CS Paper Radar

Near-Optimal Bounds for Testing Residual-String Equality and Parenthesis Languages

Hadar Strauss

cs.DS ·submitted 2026-09-28 17:56 UTC · v2
publishedtheory

Abstract

Residual-String Equality, denoted $\texttt{ResStringEq}$, is the property consisting of all pairs of strings over $\{0,1,*\}$ that are equal after deleting all `$*$' symbols from them. This property was first introduced by Fischer, Magniez, and Starikovskaya (SODA 2018), who used it to show a lower bound on testing the $\texttt{Dyck}$ languages, where $\texttt{Dyck}_m$ is the language consisting of balanced sequences of parentheses over $m$ parenthesis types. They showed that testing $\texttt{ResStringEq}$ on inputs of length $n$ requires $Ω(n^{1/5})$ queries, and presented a reduction from testing $\texttt{ResStringEq}$ to testing $\texttt{Dyck}_m$ for any $m \geq 2$. Furthermore, they showed that $\texttt{Dyck}_m$ can be tested with $O(n^{2/5+δ})$ queries for every constant proximity parameter, where $δ>0$ is an arbitrarily small constant. In this work, we nearly close the gap, by showing that testing $\texttt{ResStringEq}$, and hence $\texttt{Dyck}_m$ (for any $m\geq 2$), requires $Ω(n^{2/5})$ queries. We also show a stronger lower bound of $Ω(\sqrt{n})$ for testers that make non-adaptive queries. We establish that the $Ω(\sqrt{n})$ bound is nearly tight, by presenting a non-adaptive tester for $\texttt{ResStringEq}$ that uses $O(n^{1/2+δ})$ queries for an arbitrarily small constant $δ>0$. Furthermore, we extend this non-adaptive tester to the $\texttt{Dyck}$ languages, with the same query complexity. Finally, we improve the dependence on the proximity parameter $ε$ in the tester of Fischer, Magniez, and Starikovskaya, reducing it from $O(1/ε)^{\mathrm{poly}(1/δ)}$ to $O(1/ε)^{O(\log(1/δ))}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Query Complexity of Testing Structured Parenthesis Languages

cs.DS cs.CC ·2026-09-29 ·Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
theory similarity 0.81
Abstract

We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $Ω(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $Ω(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $Ω(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $Θ(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $Ω(n^{2/5})$ adaptive queries and $Ω(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.

0.18

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
publishedtheory similarity 0.61
Abstract · Full version of a SODA 2027 paper

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

0.47

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

Conditional Membership in Regular Languages

cs.FL ·2026-10-12 ·Antoine Amarilli, Sebastien Felipe Labbe, Charles Paperman
similarity 0.59
Abstract

We study a formulation of regular language membership as a promise problem, which we dub conditional membership: we fix a promise language $P$ and a target language $T \subseteq P$, we are given a word $w$ which is promised to belong to $P$, and we must determine whether $w$ belongs to $T$. We study the deterministic worst-case query complexity of this task, when the length $n$ of $w$ is known in advance and where each query examines the $i$-th position of $w$ for some $1 \leq i \leq n$ and returns the $i$-th letter $w_i$ of $w$. Our goal is to characterize the asymptotic complexity as a function of the word length $n$, depending on the fixed languages $P$ and $T$. Our main result is to show that the complexity of this task admits a trichotomy between three regimes: $O(1)$ queries, $Θ(\log n)$ queries, and $Θ(n)$ queries. We further show that the trichotomy criterion is decidable, namely, it is PSPACE-complete to decide which regime applies, given nondeterministic automata $A_P$ and $A_T$ respectively representing $P$ and $T$.

0.09

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.58
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Faster Regular Expression Matching via Two-Dimensional Tabulation

cs.DS ·2026-11-03 ·Philip Bille, Inge Li Gørtz
similarity 0.58
Abstract

A regular expression specifies a set of strings formed by single characters combined with concatenation, union, and Kleene star operators. Given a regular expression $R$ and a string $Q$, the classic regular expression matching problem is to decide whether $Q$ matches any string specified by $R$. Let $m$ and $n$ be the lengths of $R$ and $Q$, respectively. Our main result is a new algorithm that, given a parameter $t \geq m$, solves the problem in \[ O\left(\frac{nm\,\lg\lg(t/m)}{\lg^2(t/m)}+t+n\right) \] time and $O(t)$ words of space. In particular, for any fixed $0<\eps<1$, when $m\leq n^{1-\eps}$, we solve the problem in $O(nm \lg \lg n/\lg^2 n + m + n)$ time and $O(n)$ space. Compared to the previous best result [Bille and Thorup, ICALP 2009], this improves the leading term by a factor $\sqrt{\lg n}/\lg\lg n$. The key new technique is a two-dimensional tabulation specialized to the regular expression.

0.23

Many Scores Force Many Reads: An Optimality Proof for Score of Parentheses

cs.DS ·2026-10-09 ·Andrew Au
theory similarity 0.57
Abstract

LeetCode Problem 856, Score of Parentheses, admits a one-pass algorithm using $O(n)$ time and $O(1)$ auxiliary registers. Its correctness follows from a local interpretation: every occurrence of () contributes a power of two determined by its nesting depth. The space bound is immediately optimal in the usual programming-challenge model, but the linear-time bound is less obvious. In particular, a direct adversary that forces an algorithm to inspect every character is difficult to maintain under the promise that the input is balanced. We instead prove a counting lower bound. For every $k$, we construct $2^k$ balanced parenthesis strings of the same length $4k+2$, all having distinct scores. The construction encodes each bit using one of two operations, changing a current score $v$ to either $2v+1$ or $2v+2$. Consequently, any deterministic character-query decision tree computing the score must have depth at least $k$. A two-character padding argument extends the result to every even input length, proving an $Ω(n)$ worst-case time lower bound. The one-pass algorithm is therefore asymptotically optimal in the unit-cost RAM model.

0.29

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.57
Abstract · 32 pages

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

0.28