arXiv preprint ·
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Differentiable Exact Learning
Tensorized Automata: Algebraically Informed Representation Learning for Sequential Decision Making
Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)
Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Stochastic Games with Distributional Entropy Objectives
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.