3 papers
cs.DS2026
Hardness of Frequency-Related Queries on Compressed Strings
Rajat De, Dominik Kempa
Compressed indexing aims to support fundamental string queries in space proportional to compressed input size. For grammar compression, a length- string represented…
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…
cs.DS2025
Word Break on SLP-Compressed Texts
Rajat De, Dominik Kempa
Word Break is a prototypical factorization problem in string processing: Given a word of length and a dictionary of strings,…