betaFeedback

WorksComputer Science

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

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 ARC(x)\mathrm{ARC}(x) of an arithmetic repetition system for a word xx of length nn is at most a factor O(n1/3)O(n^{1/3}) larger than the least size ZLC(x)\mathrm{ZLC}(x) of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes O(ARC(x)log⁡n)O(\mathrm{ARC}(x)\log n) mistakes, so a polylogarithmic factor would bound its mistakes by ZLC(x) polylog(n)\mathrm{ZLC}(x)\,\mathrm{polylog}(n), which no known polynomial-time predictor achieves. We show that the optimal exponent is 1/41/4, not 1/31/3: ARC(x)≤2n1/4 ZLC(x)\mathrm{ARC}(x) \le 2n^{1/4}\,\mathrm{ZLC}(x) for every word xx, and at every large enough length nn some binary word has ARC(x)≥n1/4−o(1) ZLC(x)\mathrm{ARC}(x) \ge n^{1/4-o(1)}\,\mathrm{ZLC}(x).

Paper details

vlnc:W_ap8k5brp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus, Sonnet, Haiku 5.5, Codex

View statement
Looking for related papers…