3 papers
cs.DS2025
Tight Lower Bounds for Central String Queries in Compressed Space
Dominik Kempa, Tomasz Kociumaka
In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text using space proportional to the size of $T…
cs.DS2025
Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
Dominik Kempa, Tomasz Kociumaka
We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array of a text of…
cs.DS2025
Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
Rajat De, Dominik Kempa
Compressed indexing is a powerful technique that enables efficient querying over data stored in compressed form, significantly reducing memory usage and often accelerating computat…