Dominik Kempa

STOC Conference 2025 Conference Paper

On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM

• Dominik Kempa
• Tomasz Kociumaka

In this work, we study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms taking O ( n √log n ) time for instances described in Θ( n ) machine words (i.e., Θ( n log n ) bits). The word RAM model nowadays serves as the default model of computation for sequential algorithms, and understanding its limitations lies at the core of theoretical computer science. The class of problems solvable in O ( n √log n ) time is one of the six levels of hardness listed in the seminal paper of Chan and Pǎtraşcu [SODA 2010]. According to the current state of knowledge, this class characterizes problems from several domains, including counting inversions, string processing problems (BWT Construction, LZ77 Factorization, Longest Common Substring, Batched Longest Previous Factor Queries, Batched Inverse Suffix Array Queries), and computational geometry problems (Orthogonal Range Counting, Orthogonal Segment Intersection). Our contribution is twofold: We present several new connections between the aforementioned string problems and an old Dictionary Matching problem, which asks whether a given text contains (an exact occurrence of) at least one among the given patterns. This is a classical problem with a solution based on the Aho–Corasick automaton dating back to 1975. In this work, we restrict Dictionary Matching to instances with O ( n ) binary patterns of length m = O (log n ), short enough to be stored using O (1) machine words each, and we prove that, unless this problem can be solved faster than the current bound of O ( n √log n ), most fundamental string problems cannot be solved faster either. With further reductions, we extend this hierarchy beyond string problems, proving that computational tasks like counting inversions—a fundamental component in geometric algorithms—inherit this hardness. This, in turn, establishes the hardness of Orthogonal Range Counting and Orthogonal Segment Intersection. The key to extending our results to other domains is a surprising equivalent characterization of Dictionary Matching in terms of a new problem we call String Nesting , which, through a chain of three more reductions, can be solved by counting inversions. Put together, our results unveil a single hard problem, with two different but equivalent formulations, that underlies the hardness of nearly all known major problems, coming from different domains, currently occupying the O ( n √log n ) level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. Many of our reductions hold even for simpler versions of basic problems, such as determining the parity of the number of phrases in the LZ77 factorization or the number of runs in the BWT. This yields stronger results that can be used to design future reductions more easily. As an auxiliary outcome of our framework, we also prove that several central string problems in the RAM model do not get easier when limited to strings over the binary alphabet. Our reductions to the binary case simplify the currently fastest algorithms for many classical problems, including LZ77 Factorization and Longest Common Substring.

SODA Conference 2024 Conference Paper

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data

• Rajat De
• Dominik Kempa

FOCS Conference 2024 Conference Paper

Lempel-Ziv (LZ77) Factorization in Sublinear Time

• Dominik Kempa
• Tomasz Kociumaka

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string $T$ from left to right into blocks (called phrases) so that each phrase is either the leftmost occurrence of a single letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in the text. This simple routine has numerous applications. Most importantly, the LZ77 factorization is the central component and the computational bottleneck of most existing compression algorithms (utilized in formats like zip, pdf, and png). LZ77 is also a widely used algorithmic tool for the detection of repetitions and periodicities in strings, and the centerpiece of many powerful compressed indexes that enable computation directly over compressed data. LZ77 factorization is one of the most studied problems in string processing. In the 47 years since its inception, numerous efficient algorithms were developed for different models of computation, including parallel, GPU, external-memory, and quantum. Remarkably, however, the complexity of the most basic problem is still not settled: All existing algorithms in the RAM model run in $\Omega(n)$ time, which is a $\Theta(\log n)$ factor away from the lower bound of $\Omega(n/\log n)$ (following simply from the necessity to read the entire input, which takes $\Theta(n/\log n)$ space for any $T\in\{0, 1\}^{n})$. Sublinear-time algorithms are known for nearly all other fundamental problems on strings, but LZ77 seems resistant to all currently known techniques. We present the first $o(n)$ -time algorithm for constructing the LZ77 factorization, breaking the linear-time barrier present for nearly 50 years. More precisely, we show that, in the standard RAM model, it is possible to compute the LZ77 factorization of a given length- $n$ string $T\in \{0, 1\}^{n}$ in $\mathcal{O}(n/\sqrt{\log n})=o(n)$ time and using the optimal $O(n/\log n)$ working space. Our algorithm generalizes to larger alphabets $\Sigma=[0. . \sigma), \text{ where }\sigma=n^{\mathcal{O}2(1)}$. The runtime and working space then become $\mathcal{O}((n\log\sigma)/\sqrt{\log n})$ and $\mathcal{O}(n/\log_{\sigma}n)$, respectively. To achieve this sublinear-time LZ77 algorithm, we prove a more general result: We show that, for any constant $\epsilon\in(0, 1)$ and string $T\in[0. .\sigma)^{n}$, in $\mathcal{O}((n\log\sigma)/\sqrt{\log n})$ time and using $\mathcal{O}(n/\log_{\sigma}n)$ working space, we can construct an index of optimal size $\mathcal{O}(n/\log_{\sigma}n)$ that, given any substring $P=T[j. . j+\ell)$ specified with a pair $(j, \ell)$, computes the leftmost occurrence of $P$ in $T$ in $O(\log^{\epsilon}n)$ time. In other words, we solve the indexing/online variant of the LZ77 problem, where we can efficiently query the phrase length starting at any position. Our solution is based on a new type of queries that we call prefix range minimum queries or prefix RMQ. After developing an efficient solution for these queries, we provide a general reduction showing that any new tradeoff for the prefix RMQ implies a new tradeoff for an index finding leftmost occurrences (and hence a new LZ77 factorization algorithm).

SODA Conference 2023 Conference Paper

Breaking the 𝒪( n )-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees

• Dominik Kempa
• Tomasz Kociumaka

The suffix array, describing the lexicographical order of suffixes of a given text, and the suffix tree, a path-compressed trie of all suffixes, are the two most fundamental data structures for string processing, with plethora of applications in data compression, bioinformatics, and information retrieval. For a length- n text, however, they use Θ( n log n ) bits of space, which is often too costly. To address this, Grossi and Vitter [STOC 2000] and, independently, Ferragina and Manzini [FOCS 2000] introduced space-efficient versions of the suffix array, known as the compressed suffix array (CSA) and the FM- index. Sadakane [SODA 2002] then showed how to augment them to obtain the compressed suffix tree (CST). For a length- n text over an alphabet of size σ, these structures use only 𝒪( n log σ) bits. Nowadays, these structures are part of the standard toolbox: modern textbooks spend dozens of pages describing their applications, and they almost completely replaced suffix arrays and suffix trees in space-critical applications. The biggest remaining open question is how efficiently they can be constructed. After two decades, the fastest algorithms still run in 𝒪 (n) time [Hon et al. , FOCS 2003], which is Θ(log σ n ) factor away from the lower bound of Ω( n / log σ n ) (following from the necessity to read the input). In this paper, we make the first in 20 years improvement in n for this problem by proposing a new compressed suffix array and a new compressed suffix tree which admit o ( n )-time construction algorithms while matching the space bounds and the query times of the original CSA/CST and the FM-index. More precisely, our structures take 𝒪 (n log σ) bits, support SA queries and full suffix tree functionality in 𝒪(log ε n ) time per operation, and can be constructed in time using 𝒪 (n log σ) bits of working space. (For example, if σ = 2, the construction time is We derive this result as a corollary from a much more general reduction: We prove that all parameters of a compressed suffix array/tree (query time, space, construction time, and construction working space) can essentially be reduced to those of a data structure answering new query types that we call prefix rank and prefix selection. Using the novel techniques, we also develop a new index for pattern matching. * The full version of the paper can be accessed at https: //arxiv. org/abs/2106. 12725.

FOCS Conference 2023 Conference Paper

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space

• Dominik Kempa
• Tomasz Kociumaka

The last two decades have witnessed a dramatic increase in the amount of highly repetitive datasets consisting of sequential data (strings, texts). Processing these massive amounts of data using conventional data structures is infeasible. This fueled the development of compressed text indexes, which efficiently answer various queries on a given text, typically in polylogarithmic time, while occupying space proportional to the compressed representation of the text. There exist numerous structures supporting queries ranging from simple “local” queries, such as random access, through more complex ones, including longest common extension (LCE) queries, to the most powerful queries, such as the suffix array (SA) functionality. Alongside the rich repertoire of queries followed a detailed study of the trade-off between the size and functionality of compressed indexes (see: Navarro; ACM Comput. Surv. 2021). It is widely accepted that this hierarchy of structures tells a simple story: the more powerful the queries, the more space is needed. On the one hand, random access, the most basic query, can be supported using $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space (where n is the length of the text, $\sigma$ is the alphabet size, and $\delta$ is the text’s substring complexity), which is known to be the asymptotically smallest space sufficient to represent any string with parameters $n, \sigma$, and $\delta$ (Kociumaka, Navarro, and Prezza; IEEE Trans. Inf. Theory 2023). The other end of the hierarchy is occupied by indexes supporting the suffix array queries. The currently smallest one takes $\mathcal{O}\left(r \log \frac{n}{r}\right)$ space, where $r \geq \delta$ is the number of runs in the Burrows-Wheeler Transform of the text (Gagie, Navarro, and Prezza; J. ACM 2020). We present a new compressed index, referred to as $\delta$ SA, that supports the powerful SA functionality and needs only $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space. This collapses the hierarchy of compressed data structures into a single point: The space required to represent the text is simultaneously sufficient to efficiently support the full SA functionality. Since suffix array queries are the most widely utilized queries in string processing and data compression, our result immediately improves the space complexity of dozens of algorithms, which can now be executed in $\delta$-optimal compressed space. The $\delta$-SA supports both suffix array and inverse suffix array queries in $\mathcal{O}\left(\log ^{4+\epsilon} n\right)$ time (where $\epsilon \gt 0$ is any predefined constant). Our second main result is an $\mathcal{O}(\delta$ polylog $n)$-time construction of the $\delta$-SA from the Lempel-Ziv (LZ77) parsing of the text. This is the first algorithm that builds an SA index in compressed time, i. e. , time nearly linear in the compressed input size. For highly repetitive texts, this is up to exponentially faster than the previously best algorithm, which builds an $\mathcal{O}\left(r \log \frac{n}{r}\right)$-size index in $\mathcal{O}(\sqrt{\delta n}$ polylog $n)$ time. To obtain our results, we develop numerous new techniques of independent interest. This includes deterministic restricted recompression, $\delta$-compressed string synchronizing sets, and their construction in compressed time. We also improve many other auxiliary data structures; e. g. , we show the first $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$-size index for LCE queries along with its efficient construction from the LZ77 parsing.

SODA Conference 2022 Conference Paper

An Upper Bound and Linear-Space Queries on the LZ-End Parsing

• Dominik Kempa
• Barna Saha

Lempel–Ziv (LZ77) compression is the most commonly used lossless compression algorithm. The basic idea is to greedily break the input string into blocks (called “phrases”), every time forming as a phrase the longest prefix of the unprocessed part that has an earlier occurrence. In 2010, Kreft and Navarro introduced a variant of LZ77 called LZ-End, that additionally requires the previous occurrence of each phrase to end at the boundary of an already existing phrase. Due to its excellent practical performance as a compression algorithm and a compressed index, they conjectured that it achieves a compression that can be provably upper-bounded in terms of the LZ77 size. Despite the recent progress in understanding such relation for other compression algorithms (e. g. , the run-length encoded Burrows–Wheeler transform), no such result is known for LZ-End. We prove that for any string of length n, the number z e of phrases in the LZ-End parsing satisfies, where z is the number of phrases in the LZ77 parsing. This puts LZ-End among the strongest dictionary compressors and solves a decade-old open problem of Kreft and Navarro. Using our techniques we also derive bounds for other variants of LZ-End and with respect to other compression measures. Our second contribution is a data structure that implements random access queries to the text in space and time. This is the first linear-size structure on LZ-End that efficiently implements such queries. All previous data structures either incur a logarithmic penalty in the space or have slow queries. We also show how to extend these techniques to support longest-common-extension (LCE) queries.

STOC Conference 2022 Conference Paper

Dynamic suffix array with polylogarithmic queries and updates

• Dominik Kempa
• Tomasz Kociumaka

The suffix array SA [1. n ] of a text T of length n is a permutation of {1, …, n } describing the lexicographical ordering of suffixes of T and is considered to be one of the most important data structures for string processing, with dozens of applications in data compression, bioinformatics, and information retrieval. One of the biggest drawbacks of the suffix array is that it is very difficult to maintain under text updates: even a single character substitution can completely change the contents of the suffix array. Thus, the suffix array of a dynamic text is modelled using suffix array queries , which return the value SA [ i ] given any i ∈ [1. n ]. Prior to this work, the fastest dynamic suffix array implementations were by Amir and Boneh, who showed how to answer suffix array queries in Õ( k ) time, where k ∈ [1. n ] is a trade-off parameter, with Õ( n / k )-time text updates [ISAAC 2020]. In a very recent preprint, they also provided a solution with O (log 5 n )-time queries and Õ( n 2/3 )-time updates [arXiv 2021]. We propose the first data structure that supports both suffix array queries and text updates in O ( polylog n ) time (achieving O (log 4 n ) and O (log 3+ o (1) n ) time, respectively). Our data structure is deterministic and the running times for all operations are worst-case. In addition to the standard single-character edits (character insertions, deletions, and substitutions), we support (also in O (log 3+ o (1) n ) time) the ”cut-paste” operation that moves any (arbitrarily long) substring of T to any place in T . To achieve our result, we develop a number of new techniques which are of independent interest. This includes a new flavor of dynamic locally consistent parsing, as well as a dynamic construction of string synchronizing sets with an extra local sparsity property; this significantly generalizes the sampling technique introduced at STOC 2019. We complement our structure by a hardness result: unless the Online Matrix-Vector Multiplication (OMv) Conjecture fails, no data structure with O ( polylog n )-time suffix array queries can support the ”copy-paste” operation in O ( n 1−є ) time for any є > 0.

FOCS Conference 2020 Conference Paper

Resolution of the Burrows-Wheeler Transform Conjecture

• Dominik Kempa
• Tomasz Kociumaka

The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main component of popular lossless compression programs (such as bzip2) as well as recent powerful compressed indexes (such as r-index [Gagie et al. , J. ACM, 2020]), central in modern bioinformatics. The compression ratio of BWT is quantified by the number r of equal-letter runs. Despite the practical significance of BWT, no non-trivial bound on the value of r is known. This is in contrast to nearly all other known compression methods, whose sizes have been shown to be either always within a polylogn factor (where n is the length of text) from z, the size of Lempel-Ziv (LZ77) parsing of the text, or significantly larger in the worst case (by a n ε factor for ). In this paper, we show that r=O(zlog 2 n) holds for every text. This result has numerous implications for text indexing and data compression; for example: (1) it proves that many results related to BWT automatically apply to methods based on LZ77, e. g. , it is possible to obtain functionality of the suffix tree in O(zpolylog n) space; (2) it shows that many text processing tasks can be solved in the optimal time assuming the text is compressible using LZ77 by a sufficiently large polylogn factor; (3) it implies the first non-trivial relation between the number of runs in the BWT of the text and its reverse. In addition, we provide an O(z polylog n)-time algorithm converting the LZ77 parsing into the run-length compressed BWT. To achieve this, we develop a number of new data structures and techniques of independent interest. In particular, we introduce a notion of compressed string synchronizing sets (generalizing the recently introduced powerful technique of string synchronizing sets [STOC 2019]) and show how to efficiently construct them. Next, we propose a new variant of wavelet trees for sequences of long strings, establish a nontrivial bound on their size, and describe efficient construction algorithms. Finally, we describe new indexes that can be constructed directly from the LZ77-compressed text and efficiently support pattern matching queries on substrings of the text.

SODA Conference 2019 Conference Paper

Optimal Construction of Compressed Indexes for Highly Repetitive Texts

• Dominik Kempa

We propose algorithms that, given the input string of length n over integer alphabet of size σ, construct the Burrows–Wheeler transform (BWT), the permuted longest-common-prefix (PLCP) array, and the LZ77 parsing in O ( n/ log σ n + r polylog n ) time and working space, where r is the number of runs in the BWT of the input. These are the essential components of many compressed indexes such as compressed suffix tree, FM-index, and grammar and LZ77-based indexes, but also find numerous applications in sequence analysis and data compression. The value of r is a common measure of repetitiveness that is significantly smaller than n if the string is highly repetitive. Since just accessing every symbol of the string requires Ω( n / log σ n ) time, the presented algorithms are time and space optimal for inputs satisfying the assumption n / r ∊ Ω(polylog n ) on the repetitiveness. For such inputs our result improves upon the currently fastest general algorithms of Belazzougui (STOC 2014) and Munro et al. (SODA 2017) which run in O ( n ) time and use O ( n / log σ n ) working space. We also show how to use our techniques to obtain optimal solutions on highly repetitive data for other fundamental string processing problems such as: Lyndon factorization, construction of run-length compressed suffix arrays, and some classical “textbook” problems such as computing the longest substring occurring at least some fixed number of times.

STOC Conference 2019 Conference Paper

String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure

• Dominik Kempa
• Tomasz Kociumaka

STOC Conference 2018 Conference Paper

At the roots of dictionary compression: string attractors

• Dominik Kempa
• Nicola Prezza

TCS Journal 2016 Journal Article

Tighter bounds for the sum of irreducible LCP values

• Juha Kärkkäinen
• Dominik Kempa
• Marcin Pia̧tkowski

The suffix array is frequently augmented with the longest-common-prefix (LCP) array that stores the lengths of the longest common prefixes between lexicographically adjacent suffixes of a text. While the sum of the values in the LCP array can be Ω ( n 2 ) for a text of length n, the sum of so-called irreducible LCP values was shown to be O ( n lg ⁡ n ) a few years ago. In this paper, we improve the bound to O ( n lg ⁡ r ), where r ≤ n is the number of runs in the Burrows–Wheeler transform of the text. We also show that our bound is tight up to lower order terms (unlike the previous bound). Our results and the techniques used in proving them provide new insights into the combinatorics of text indexing and compression, and have immediate applications to LCP array construction algorithms.