Author

Tomasz Kociumaka

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

For a text $T\in[0..\sigma)^n$ with $2\leq\sigma\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(...

Dominik Kempa, Tomasz Kociumaka · 1 citation

Preprint Aug 2026

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

For a text $T$ of length $n$ over an alphabet of size $\sigma$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix...

Dominik Kempa, Tomasz Kociumaka · 1 citation