The Complexity of Dynamic LZ77 is Θ ~ ( n 2 / 3 ) \tilde{\Theta}(n^{2/3})
Itai Boneh, Shay Golan, Matan Kraus · 2025
Read The Complexity of Dynamic LZ77 is Θ ~ ( n 2 / 3 ) \tilde{\Theta}(n^{2/3}) by Itai Boneh, Shay Golan, Matan Kraus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12000.txt.
Introduction
Itai Boneh, Shay Golan, and Matan Kraus settle the cost of keeping a classic compression scheme up to date in a 2025 paper. The scheme, LZ77, splits text into pieces copied from earlier text. Editors change text constantly, so the split must be maintained live.
The authors give an algorithm that builds the split in near-linear time. Each edit then costs about the two-thirds power of the text length, up to log factors. They also prove no method can do much better, unless a famed math guess fails. The lower bound holds even if only swaps are allowed and only the split's length is tracked. Upper and lower bounds meet, closing the problem.
Catalog record
| CREATOR | Itai Boneh, Shay Golan, Matan Kraus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12000