CS Paper Radar

Beyond Typical Strings: Sampling the Complexity Landscape

Abdurrahman Hadi Erturk, Joshua Sharkey, Nora S Martin, Kamal Dingle, Ard A Louis

cs.IT ·submitted 2026-10-30 10:31 UTC · v2

Abstract

Uniform random sampling of strings is overwhelmingly dominated by high-complexity strings, leaving the much smaller set of low- and intermediate-complexity strings largely unexplored. Here, we adapt the nested neutral set estimator (NNSE), a Monte Carlo rare-event sampling method, to estimate the distribution P(K) of complexity values for binary strings of fixed length. NNSE allows us to explore the full complexity landscape, including exponentially rare low-complexity regions that are inaccessible to direct sampling, for string lengths up to several hundred. We apply the method to several widely used complexity measures: Lempel-Ziv 76 (LZ76), Lempel-Ziv 78 (LZ78), context tree weighting (CTW), the block decomposition method (BDM), and block entropy. We further introduce uniform complexity weighting (UCW), which gives equal weight to different complexity levels rather than to individual strings. Using NNSE to perform UCW sampling allows us to compare complexity measures across their full range in a dataset-independent way. This reveals differences in their behavior for low- and intermediate-complexity strings that are practically inaccessible to conventional uniform sampling.

Closest papers

Nearest neighbours by meaning across the whole index.

Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity

cs.FL cs.DScs.LG ·2026-09-17 ·Vanessa Kosoy
similarity 0.61
Abstract

In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.

0.45

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.59
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

A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics

cs.DS ·2026-09-14 ·Ethan Mader, Borna Tavasoli, Jihan Wang
similarity 0.58
Abstract

We study weighted edit distance between two strings of total length $n$, where edit costs are induced by an arbitrary metric. For equal-length inputs, Kuszmaul (2019) gave an $O(n^δ)$-approximation with $\widetilde{O}(n^{2-δ})$ running time for every fixed $0 < δ< 1$. We give the first constant-factor approximation for weighted edit distance over arbitrary metrics in strongly subquadratic running time. For every $0 < \varepsilon \le 1$, our randomized algorithm runs in $\widetilde{O}(n^{7/4}/\varepsilon^8)$ time and returns a $(3+\varepsilon)$-approximation with probability at least $1-n^{-10}$. The algorithm allows unequal input lengths and places no bound on the ratio between edit costs.

0.20

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

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.57
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

The Complexity of Unpredictability

cs.CC ·2026-11-04 ·Aryan Agarwala, Dani Dorfman
theory similarity 0.57
Abstract

We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $ε>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+ε$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.

0.26

Universal Random Coding for Successive Refinement of Individual Sequences Based on Lempel-Ziv Complexity

cs.IT ·2026-08-25 ·Neri Merhav
published similarity 0.57
Abstract · 35 pages; to be submitted

This work extends an earlier proposed universal random-coding ensemble for sample-wise lossy compression of individual sequences to the two-stage (successive-refinement) setting --- an extension that is not quite straightforward, as explained in the sequel. The construction has three layers. First, a complete, self-contained direct/converse match in the language of type classes and typical sequences, a two-stage analogue of Rimoldi's classical characterization (applied in the superalphabet of blocks). Second, a realization of the same rates via a random-coding scheme built from the Lempel--Ziv (LZ78) complexity rather than the type-class uniform measure the first layer relies on, since an LZ-based ensemble is universal across source statistics and distortion measures, carries no block-length parameter in the codebook itself, and is directly implementable. Third, we give a fully type-free achievability construction (no joint types of $\ell$-vectors appear anywhere in its search criterion) and show it matches the same converse exactly, reaching every point of the achievable region: the same converse from the first layer already binds any code, type-free schemes included, so no separate argument is needed to certify the match. We also describe (without proof) how to extend the type-free construction to any fixed number $r>2$ of stages. Finally, we show this paper's achievable region is a superset of the one obtained by a companion paper, which is based on a finite-state modeling approach to a similar two-stage problem, extending a known single-stage domination result to two stages.

0.29

Exact Algorithms and Complexity of the Smallest Grammar Problem

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