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

CREATORItai Boneh, Shay Golan, Matan Kraus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE156 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12000

Browse the full library · About the Tower of Babel