Tomasz Kociumaka

collaborators

6 papers

cs.DS2026

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes

Anouk Duyster, Tomasz Kociumaka

A Random Access query to a string $T \in [0.. I ¨ )^{n}$ asks for the character $T [i]$ at a given position $i \in [0.. n)$ . In $O (n lo g I ¨ )$ bits of space, this fundamental task admits cons…

cs.DS2026

The Communication Complexity of Pattern Matching with Edits Revisited

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

In the decades-old Pattern Matching with Edits problem, given a length- $n$ string $T$ (the text), a length- $m$ string $P$ (the pattern), and a positive integer $k$ (the threshold),…

cs.DS2026

Time-Optimal Construction of String Synchronizing Sets

Jonas Ellert, Tomasz Kociumaka

A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka;…

cs.DS2025

Pattern Matching under Weighted Edit Distance

Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz

In Pattern Matching with Weighted Edits (PMWED), we are given a pattern $P$ of length $m$ , a text $T$ of length $n$ , a positive threshold $k$ , and oracle access to a weight functio…

cs.DS2025

Near-Optimal Property Testers for Pattern Matching

Ce Jin, Tomasz Kociumaka

The classic exact pattern matching problem, given two strings -- a pattern $P$ of length $m$ and a text $T$ of length $n$ -- asks whether $P$ occurs as a substring of $T$ . A proper…

cs.DS2025

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts

Anouk Duyster, Tomasz Kociumaka

Internal Pattern Matching (IPM) queries on a text $T$ , given two fragments $X$ and $Y$ of $T$ such that $∣ Y ∣ < 2∣ X ∣$ , ask to compute all exact occurrences of $X$ within $Y$ . IPM quer…