CS Paper Radar

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

Matthias G. Mayer

cs.DS cs.FL ·submitted 2026-11-16 12:14 UTC · v1
code/data

Abstract

Two classical ways to compress a word are straight-line programs (SLPs), which build it by concatenating smaller pieces, and the Lempel-Ziv 77 (LZ77) factorisation, which copies earlier parts of it; their sizes are measures of repetitiveness. LZ77 approximates the smallest SLP efficiently: it has no more factors than a smallest SLP has size, and yields an SLP at most a logarithmic factor larger in near-linear time. Motivated by online prediction, Kosoy introduced zipline programs, which are analogous to SLPs but interleave their pieces round-robin instead of concatenating them. Her generalisation of LZ77, the arithmetic repetition system, describes a word by copies from one arithmetic progression of positions to a later one. Do arithmetic repetition systems approximate the smallest zipline program as well? Kosoy proved that the least size $\mathrm{ARC}(x)$ of an arithmetic repetition system for a word $x$ of length $n$ is at most a factor $O(n^{1/3})$ larger than the least size $\mathrm{ZLC}(x)$ of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes $O(\mathrm{ARC}(x)\log n)$ mistakes, so a polylogarithmic factor would bound its mistakes by $\mathrm{ZLC}(x)\,\mathrm{polylog}(n)$, which no known polynomial-time predictor achieves. We show that the optimal exponent is $1/4$, not $1/3$: $\mathrm{ARC}(x) \le 2n^{1/4}\,\mathrm{ZLC}(x)$ for every word $x$, and at every large enough length $n$ some binary word has $\mathrm{ARC}(x) \ge n^{1/4-o(1)}\,\mathrm{ZLC}(x)$.

Comment
45 pages. Lean 4 formalisation: https://github.com/matthiasGmayer-research/copying-vs-interleaving-lean

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Lempel-Ziv Prediction with the Run-Length BWT

cs.DS cs.LG ·2026-11-01 ·Ohad Avnery
similarity 0.65
Abstract · 21 pages, 1 table

Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.

0.25

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

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

cs.DS ·2026-09-24 ·Jonas Ellert, Lukas Nalbach
similarity 0.61
Abstract · 17 pages, 6 figures, 4 tables. Full version of the ALENEX 2027 paper

The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number $z$ of phrases that each refer to an earlier occurrence. It is this phrase count, rather than the encoded size, that governs the size of LZ-based compressed indexes, and computing a factorization with few phrases is a time and space bottleneck in their construction. In practice, computing LZ77 quickly typically requires the suffix array. In theory, the exact LZ77 factorization, and a 3-approximation of it, can be computed more space-efficiently without the full suffix array [SPIRE 2023]. These algorithms have remained unimplemented, because two of their components resist a direct implementation: a lookup table that degenerates to patterns of length at most two for realistic inputs, and an orthogonal range reporting data structure that is impractical. We replace both, fine-tune every remaining stage, and obtain the first practical implementation, which runs in space close to the text rather than to the suffix array. On one thread, our 3-approximation factorizes 12-19x faster than the classical LPF algorithm while using 14x less memory; on 32 threads, even our exact algorithm is 1.4-2.9x faster than parallel LPF, at 9x less memory. In practice the approximation ratio stays far below 3. As a side result, passing only the perfect phrases of our 3-approximation to a downstream compressor yields a precompressor that is on par with the state of the art [Dinklage, SEA 2026] in compression ratio, and better in memory consumption and parallel throughput.

0.19

The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats

cs.DC cs.DS ·2026-09-15 ·Yakiv Shavidze
similarity 0.57
Abstract · 7 pages, 5 figures, 6 tables. Sixth paper in the ACEAPEX series (see arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541, 2608.10188). Code…

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

0.50

Lempel-Ziv Parsing with Match-Length-Dependent Windows: Universality and Limits

cs.IT ·2026-10-05 ·Yingquan, Wu
similarity 0.57
Abstract · 39 pages, 4 figures, 3 tables. v2: rewritten for clarity, with a new title (v1 was "Improved LZ77 Compression with Match-Length-Dependent Sl…

LZ77 coders spend the same number of bits on the distance of every match, although short matches rarely pay off at long distances. With match-length-dependent windows, used in several practical codecs, a match of length $\ell$ may refer back at most $W(\ell)$ symbols: short matches get short distance fields, while long matches keep the full window $W$. This breaks the suffix closure that classical LZ77 analyses rely on: the tail of an admissible match need not be admissible. We bound the cost of this loss, and of matches missed by a practical hash search, by the phrase count of a single-window reference parse. Consequently, when the full window starts at length $O(\log W)$, greedy parsing keeps the convergence rates and the optimal finite-input rates of LZ77 under substring-complexity constraints, and when it starts at length $o(\log W)$, greedy parsing is universal for stationary ergodic sources. We then delimit what the windows gain. A calibrated schedule never increases the minimum code length and saves a polynomially small rate on some iid sources. The leading redundancy term is set by the length code instead: on uniform iid data, with logarithmic-cost lengths and a fixed full-window threshold, it is at least of order $(\log\log W)/\log W$ whatever windows the short matches use, and a short codeword for a growing longest match reduces it to $O((\log\log\log W)/\log W)$. We also quantify the gains of coding single-symbol runs by count and of Huffman coding the token fields, and obtain a consistent entropy-rate estimator by selecting the window.

0.50

A Non-constant Lower Bound for Grammar-Based Compression with Greedy

cs.DS cs.FL ·2026-09-10 ·Danny Hucke
theory similarity 0.57
Abstract

We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

0.25

Massively Parallel Algorithms for Huffman Coding

cs.DS ·2026-10-06 ·Masoud Seddighin, Saeed Seddighin
similarity 0.56
Abstract

Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length of the string is minimized. Huffman coding is widely used in practical compression systems, including file compression. As modern datasets continue to grow, it is natural to study whether a Huffman code can be constructed efficiently in the massively parallel computation (\MPC) model. The celebrated Huffman coding algorithm admits two straightforward \MPC implementations: for any constant $ε\in(0,1)$, one uses $O(\TextLength^ε)$ memory per machine but requires $Θ(\log \TextLength)$ rounds, while the other runs in $O(1)$ rounds but requires $Θ(\sqrt{\TextLength})$ memory per machine. We give the first nontrivial \MPC algorithm for Huffman coding that bypasses both limitations. For every constant $ε>0$, our algorithm uses $O_ε(\log\log \TextLength)$ rounds and $\softO(\TextLength^ε)$ memory per machine, while its total memory and total computation are $\softO(\TextLength)$. {\color{black}Although our framework is tailored to the \MPC model, we show that it has applications in the \PRAM setting as well. Specifically, we show that the same algorithm can be implemented in the \PRAM model with total work close to linear. In particular, whenever the text length is at most $2^{O\left(\left(\frac{\log \AlphabetSize}{\log\log \AlphabetSize}\right)^2\right)}$ (slightly superpolynomial), where $\AlphabetSize$ is the alphabet size, our parallel running time is asymptotically better than that of all previously known \PRAM algorithms and is essentially optimal.}

0.26

Where Induction Runs Out: Description-Length Difficulty and the Memorisation Gap in Integer-Sequence Benchmarks

cs.LG cs.SC ·2026-08-29 ·Sabilashan Ganeshan
benchmarkcode/data similarity 0.55
Abstract · 14 pages, 6 figures. Code and data: https://github.com/sabilashang/where-induction-runs-out. Archived: doi:10.5281/zenodo.21830331

Integer sequences from the On-Line Encyclopedia of Integer Sequences (OEIS) are increasingly used to benchmark mathematical reasoning in language models. We ask what such benchmarks actually measure, using an exactly computable reference learner: two-part minimum description length (MDL) over the class of P-recursive (holonomic) recurrences, evaluated on every prefix of a sequence as terms arrive. Three findings follow. First, MDL difficulty is a parameter count. The discovery point nd, the first prefix length at which a symbolic hypothesis beats verbatim storage, is predicted almost exactly by a combinatorial identifiability bound on the selected operator's order and degree. It is invariant to term magnitude: scaling Fibonacci over twelve orders of magnitude leaves nd unchanged, because a hypothesis must encode its own initial conditions and the magnitude cancels. Second, at scale the learner exhibits a regime our curated corpus could not produce even once: across 20,000 OEIS sequences, 89.98% of those that fit a recurrence on some prefix fit none at full length. We call this the wilderness -- induction acquires a theory, loses it, and never recovers. Third, evaluating three language models on sequences stratified by these MDL regimes refuted our pre-registered hypothesis: models do not confabulate where MDL reports no theory, but hedge appropriately. Confident errors are inverted, concentrating on the easy stratum, where apparent competence tracks recognition of the sequence rather than induction of its rule. OEIS-derived benchmarks therefore substantially measure memorisation, and MDL supplies a cheap, contamination-free difficulty signal they currently lack. Code and data are released.

0.37