39 citations · 241 across the 54 of their papers we have counts for
7 papers · 1 filter
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…