Reproduce “On the complexity and approximability of Bounded access Lempel Ziv coding” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Ferdinando Cicalese, Francesca Ugazio

Researchers from the University of Verona provide a theoretical analysis of Bounded Access Lempel Ziv (BLZ) coding, demonstrating that finding an optimal c-BLZ parsing is NP-hard and APX-hard for any constant `c`. The work reveals a worst-case unbounded ratio between optimal c-BLZ and standard LZ76 parsing, quantifying the trade-off between random access capability and compression efficiency.

Key insights

  • Finding an optimal c-BLZ parsing is computationally intractable (NP-hard and APX-hard) for any constant `c`, meaning exact polynomial-time solutions are unlikely, and even arbitrary approximations are impossible under standard complexity assumptions.
  • A fundamental trade-off exists between enforcing fast random access and achieving high compression, as c-BLZ can result in significantly more phrases than standard LZ76 for certain types of strings.
  • The theoretical hardness results guide future algorithm design, focusing efforts on approximation algorithms or heuristics rather than optimal polynomial-time solutions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.