← 研踪 PaperTrailarXiv:2611.20980 · v1
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
首次提交 2026-11-16 20:14
版本更新 2026-11-16 20:14
雷达观测 2026-11-17 17:11
摘要
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 of an arithmetic repetition system for a word of length is at most a factor larger than the least size of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes mistakes, so a polylogarithmic factor would bound its mistakes by , which no known polynomial-time predictor achieves. We show that the optimal exponent is , not : for every word , and at every large enough length some binary word has .
作者备注:45 pages. Lean 4 formalisation: https://github.com/matthiasGmayer-research/copying-vs-interleaving-lean
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 20:14 · 最新观测版本
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
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 of an arithmetic repetition system for a word of length is at most a factor larger than the least size of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes mistakes, so a polylogarithmic factor would bound its mistakes by , which no known polynomial-time predictor achieves. We show that the optimal exponent is , not : for every word , and at every large enough length some binary word has .
查看此版本解读 →查看此版本原文 ↗