Papers for

compression algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Pair merge compression hard to approximate on binary and unary strings

Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

Abstract: Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose $k$ merges that leave a string of length $n$ almost as short as possible; doing nothing is already within a factor $n$. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor $c\,n/\log n$, for some constant $c>0$, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that $k$ merges form a grammar with $k$ rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves $O(n/\log\log n)$, and no Karp reduction can prove hardness beyond order $n/\log n$ unless coNP $\subseteq$ NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on datasets with repeated strings.

Tue 10 NovData Structures and AlgorithmsComputational ComplexityComputation and Language
The gist
The paper studies the difficulty of compressing strings by merging pairs of symbols, a common approach in text tokenisation. The authors show that finding near-optimal merges efficiently is very hard—even for simple binary strings—unless widely believed complexity assumptions fail. They also prove that on single-letter (unary) datasets, the problem of finding optimal merges is strongly NP-complete, meaning it remains hard even when numeric values are small. This clarifies the computational limits of some popular tokenisation strategies.
Open → 2611.13568v1

Logarithmic gap found between LZ77 and grammar compression methods

Logarithmic Separation between LZ77 and LZ-End and Grammar Compression

Abstract: We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.

Fri 23 OctInformation TheoryData Structures and Algorithms
The gist
The paper finds that one popular data compression method, called LZ77, can compress some data much more efficiently than two other methods called LZ-End and grammar compression. Specifically, the difference in how compact the results are can grow like the logarithm of the input size, meaning the gap can be significantly large as data gets bigger. The authors establish this by proving a theoretical limit, showing these methods are not equally powerful for all inputs.
Open → 2610.32818v1