Tomasz Kociumaka

research

∙ 08/07/2023

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space

In the last decades, the necessity to process massive amounts of textual...

0 Dominik Kempa, et al. ∙

research

∙ 07/14/2023

Approximating Edit Distance in the Fully Dynamic Model

The edit distance is a fundamental measure of sequence similarity, defin...

0 Tomasz Kociumaka, et al. ∙

research

∙ 05/11/2023

Optimal Algorithms for Bounded Weighted Edit Distance

The edit distance of two strings is the minimum number of insertions, de...

0 Alejandro Cassis, et al. ∙

research

∙ 02/08/2023

Weighted Edit Distance Computation: Strings, Trees and Dyck

Given two strings of length n over alphabet Σ, and an upper bound k on t...

0 Debarati Das, et al. ∙

research

∙ 11/22/2022

An Algorithmic Bridge Between Hamming and Levenshtein Distances

The edit distance between strings classically assigns unit cost to every...

0 Elazar Goldenberg, et al. ∙

research

∙ 11/14/2022

Bellman-Ford is optimal for shortest hop-bounded paths

This paper is about the problem of finding a shortest s-t path using at ...

0 Tomasz Kociumaka, et al. ∙

research

∙ 09/15/2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

Computing the edit distance of two strings is one of the most basic prob...

0 Debarati Das, et al. ∙

research

∙ 08/18/2022

Approximate Circular Pattern Matching

We consider approximate circular pattern matching (CPM, in short) under ...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 06/01/2022

Near-Optimal Search Time in δ-Optimal Space

Two recent lower bounds on the compressiblity of repetitive sequences, δ...

0 Tomasz Kociumaka, et al. ∙

research

∙ 04/06/2022

Faster Pattern Matching under Edit Distance

We consider the approximate pattern matching problem under the edit dist...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 01/18/2022

Computing Longest (Common) Lyndon Subsequences

Given a string T with length n whose characters are drawn from an ordere...

0 Hideo Bannai, et al. ∙

research

∙ 01/04/2022

Dynamic Suffix Array with Polylogarithmic Queries and Updates

The suffix array SA[1..n] of a text T of length n is a permutation of {1...

0 Dominik Kempa, et al. ∙

research

∙ 12/10/2021

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding

The Dyck language, which consists of well-balanced sequences of parenthe...

0 Debarati Das, et al. ∙

research

∙ 12/10/2021

How Compression and Approximation Affect Efficiency in String Distance Measures

Real-world data often comes in compressed form. Analyzing compressed dat...

0 Arun Ganesh, et al. ∙

research

∙ 11/24/2021

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal

We study the problem of approximating edit distance in sublinear time. T...

0 Elazar Goldenberg, et al. ∙

research

∙ 11/03/2021

An Improved Algorithm for The k-Dyck Edit Distance Problem

A Dyck sequence is a sequence of opening and closing parentheses (of var...

0 Dvir Fried, et al. ∙

research

∙ 06/24/2021

Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays

The suffix array, describing the lexicographic order of suffixes of a gi...

0 Dominik Kempa, et al. ∙

research

∙ 06/10/2021

Small space and streaming pattern matching with k edits

In this work, we revisit the fundamental and well-studied problem of app...

0 Tomasz Kociumaka, et al. ∙

research

∙ 05/13/2021

The Dynamic k-Mismatch Problem

The text-to-pattern Hamming distances problem asks to compute the Hammin...

0 Raphael Clifford, et al. ∙

research

∙ 05/07/2021

Faster Algorithms for Longest Common Substring

In the classic longest common substring (LCS) problem, we are given two ...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 11/21/2020

Improved Dynamic Algorithms for Longest Increasing Subsequence

We study dynamic algorithms for the longest increasing subsequence (LIS)...

0 Tomasz Kociumaka, et al. ∙

research

∙ 08/30/2020

Tight Bound for the Number of Distinct Palindromes in a Tree

For an undirected tree with n edges labelled by single letters, we consi...

0 Paweł Gawrychowski, et al. ∙

research

∙ 07/24/2020

Sublinear-Time Algorithms for Computing Embedding Gap Edit Distance

In this paper, we design new sublinear-time algorithms for solving the g...

0 Tomasz Kociumaka, et al. ∙

research

∙ 06/24/2020

Improved Circular k-Mismatch Sketches

The shift distance 𝗌𝗁(S_1,S_2) between two strings S_1 and S_2 of the sa...

0 Shay Golan, et al. ∙

research

∙ 05/12/2020

Counting Distinct Patterns in Internal Dictionary Matching

We consider the problem of preprocessing a text T of length n and a dict...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 04/28/2020

Approximating longest common substring with k mismatches: Theory and practice

In the problem of the longest common substring with k mismatches we are ...

0 Garance Gourdel, et al. ∙

research

∙ 04/27/2020

The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time

We revisit the k-mismatch problem in the streaming model on a pattern of...

0 Shay Golan, et al. ∙

research

∙ 04/17/2020

Faster Approximate Pattern Matching: A Unified Approach

Approximate pattern matching is a natural and well-studied problem on st...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 03/04/2020

Time-Space Tradeoffs for Finding a Long Common Substring

We consider the problem of finding, given two documents of total length ...

0 Stav Ben Nun, et al. ∙

research

∙ 01/01/2020

Approximating Text-to-Pattern Hamming Distances

We revisit a fundamental problem in string matching: given a pattern of ...

0 Timothy M. Chan, et al. ∙

research

∙ 10/23/2019

Resolution of the Burrows-Wheeler Transform Conjecture

Burrows-Wheeler Transform (BWT) is an invertible text transformation tha...

0 Dominik Kempa, et al. ∙

research

∙ 10/04/2019

Towards a Definitive Measure of Repetitiveness

Unlike in statistical compression, where Shannon's entropy is a definiti...

0 Tomasz Kociumaka, et al. ∙

research

∙ 09/25/2019

Internal Dictionary Matching

We introduce data structures answering queries concerning the occurrence...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 09/25/2019

Weighted Shortest Common Supersequence Problem Revisited

A weighted string, also known as a position weight matrix, is a sequence...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 07/03/2019

Circular Pattern Matching with k Mismatches

The k-mismatch problem consists in computing the Hamming distance betwee...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 06/13/2019

On Longest Common Property Preserved Substring Queries

We revisit the problem of longest common property preserving substring q...

0 Kazuki Kai, et al. ∙

research

∙ 05/03/2019

RLE edit distance in near optimal time

We show that the edit distance between two run-length encoded strings of...

0 Raphael Clifford, et al. ∙

research

∙ 04/08/2019

String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure

Burrows-Wheeler transform (BWT) is an invertible text transformation tha...

0 Dominik Kempa, et al. ∙

research

∙ 02/28/2019

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

We investigate the locality number, a recently introduced structural par...

0 Katrin Casel, et al. ∙

research

∙ 01/31/2019

Quasi-Linear-Time Algorithm for Longest Common Circular Factor

We introduce the Longest Common Circular Factor (LCCF) problem in which,...

0 Mai Alzamel, et al. ∙

research

∙ 12/19/2018

Efficient Representation and Counting of Antipower Factors in Words

A k-antipower (for k > 2) is a concatenation of k pairwise distinct word...

0 Tomasz Kociumaka, et al. ∙

research

∙ 07/31/2018

Efficient Computation of Sequence Mappability

Sequence mappability is an important task in genome re-sequencing. In th...

0 Mai Alzamel, et al. ∙

research

∙ 07/27/2018

Faster Recovery of Approximate Periods over Edit Distance

The approximate period recovery problem asks to compute all approximate ...

0 Tomasz Kociumaka, et al. ∙

research

∙ 05/24/2018

Longest Unbordered Factor in Quasilinear Time

A border u of a word w is a proper factor of w occurring both as a prefi...

0 Tomasz Kociumaka, et al. ∙

research

∙ 04/18/2018

On Abelian Longest Common Factor with and without RLE

We consider the Abelian longest common factor problem in two scenarios: ...

0 Szymon Grabowski, et al. ∙

research

∙ 02/18/2018

Linear-Time Algorithm for Long LCF with k Mismatches

In the Longest Common Factor with k Mismatches (LCF_k) problem, we are g...

0 Panagiotis Charalampopoulos, et al. ∙

research

∙ 01/04/2018

String Periods in the Order-Preserving Model

The order-preserving model (op-model, in short) was introduced quite rec...

0 Garance Gourdel, et al. ∙

research

∙ 01/03/2018

On Periodicity Lemma for Partial Words

We investigate the function L(h,p,q), called here the threshold function...

0 Tomasz Kociumaka, et al. ∙

research

∙ 12/22/2017

Longest common substring with approximately k mismatches

In the longest common substring problem we are given two strings of leng...

0 Tomasz Kociumaka, et al. ∙

Tomasz Kociumaka

Featured Co-authors