39 citations · 241 across the 54 of their papers we have counts for
83 papers · 1 filter
Space-Efficient k-Mismatch Text Indexes
Tomasz Kociumaka, Jakub Radoszewski
A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length ) into an efficient index (a data structure) supporting queries…
Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text of length , a pattern of length , and a threshold , the task is to…
On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
The decades-old Pattern Matching with Edits problem, given a length- string (the text), a length- string (the pattern), and a positive integer (the threshold), as…
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka +1
Classically, the edit distance of two length- strings can be computed in time, whereas an -time procedure would falsify the Orthogonal Vectors Hypothesis. I…
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most funda…
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
Dominik Kempa, Tomasz Kociumaka
In the last decades, the necessity to process massive amounts of textual data fueled the development of compressed text indexes: data structures efficiently answering queries on a…
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one strin…
Optimal Algorithms for Bounded Weighted Edit Distance
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
The edit distance of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic…
Weighted Edit Distance Computation: Strings, Trees and Dyck
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
Given two strings of length over alphabet , and an upper bound on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes…
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1
The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In…
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
Approximate Circular Pattern Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +4
We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length- text , a length- pattern , and a…
Near-Optimal Search Time in -Optimal Space, and Vice Versa
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Two recent lower bounds on the compressibility of repetitive sequences, , have received much attention. It has been shown that a length- string over an alphabet of s…
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
We consider the approximate pattern matching problem under the edit distance. Given a text of length , a pattern of length , and a threshold , the task is to find…
Computing Longest (Common) Lyndon Subsequences
Hideo Bannai, Tomohiro I, Tomasz Kociumaka +2
Given a string with length whose characters are drawn from an ordered alphabet of size , its longest Lyndon subsequence is a longest subsequence of that is a Lyndon…
Dynamic Suffix Array with Polylogarithmic Queries and Updates
Dominik Kempa, Tomasz Kociumaka
The suffix array of a text of length is a permutation of describing the lexicographical ordering of suffixes of , and it is considered to be…
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
Debarati Das, Tomasz Kociumaka, Barna Saha
The Dyck language, which consists of well-balanced sequences of parentheses, is one of the most fundamental context-free languages. The Dyck edit distance quantifies the number of…
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer +1
We study the problem of approximating edit distance in sublinear time. This is formalized as the -Gap Edit Distance problem, where the input is a pair of strings and…
An Improved Algorithm for The -Dyck Edit Distance Problem
Dvir Fried, Shay Golan, Tomasz Kociumaka +3
A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses is the smallest…
Small space and streaming pattern matching with k edits
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
In this work, we revisit the fundamental and well-studied problem of approximate pattern matching under edit distance. Given an integer , a pattern of length , and a text…
Breaking the -Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
Dominik Kempa, Tomasz Kociumaka
The suffix array and the suffix tree are the two most fundamental data structures for string processing. For a length- text, however, they use bits of space, which…
The Dynamic k-Mismatch Problem
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length and all length- substrings of a given text of length $n…
Faster Algorithms for Longest Common Substring
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +1
In the classic longest common substring (LCS) problem, we are given two strings and , each of length at most , over an alphabet of size , and we are asked to find a lo…
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka, Saeed Seddighin
We study dynamic algorithms for the longest increasing subsequence (\textsf{LIS}) problem. A dynamic \textsf{LIS} algorithm maintains a sequence subject to operations of the follow…