52 citations · 133 across the 25 of their papers we have counts for
38 papers
Streaming algorithms for computing coresets and -median clustering in the Hamming space
Taha El Ghazi, Jonas Ellert, Chien-Chung Huang +1
Clustering is one of the most fundamental tools in data analysis, allowing large datasets to be summarized by a small number of representative points. Given a metric space $(\mathc…
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert +2
Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorit…
Streaming periodicity with mismatches, wildcards, and edits
Taha El Ghazi, Tatiana Starikovskaya
In this work, we study the problem of detecting periodic trends in strings. While detecting exact periodicity has been studied extensively, real-world data is often noisy, where sm…
Faster two-dimensional pattern matching with mismatches
Jonas Ellert, Paweł Gawrychowski, Adam Górkiewicz +1
The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters.…
Small Space Encoding and Recognition of -Palindromic Prefixes
Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindrome…
Longest Common Extensions with Wildcards: Trade-off and Applications
Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos +2
We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other c…
Internal Pattern Matching in Small Space and Applications
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our mai…
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
Pattern Matching with Mismatches and Wildcards
Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya
In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern of length containing wildcards, a text of length , and an in…
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…
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
Given a signed permutation on elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomic…
Compressed Indexing for Consecutive Occurrences
Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya +1
The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient s…
Pattern matching under DTW distance
Garance Gourdel, Anne Driemel, Pierre Peterlongo +1
In this work, we consider the problem of pattern matching under the dynamic time warping (DTW) distance motivated by potential applications in the analysis of biological data produ…
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…
Approximating longest common substring with mismatches: Theory and practice
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski +1
In the problem of the longest common substring with mismatches we are given two strings and must find the maximal length such that there is a length- substr…
Generalised Pattern Matching Revisited
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
In the problem of [STOC'94, Muthukrishnan and Palem], we are given a text of length over an alphabet , a patter…
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements su…
Sliding window property testing for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey +1
We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the…
Pattern Matching in a Stream
Tatiana Starikovskaya, Michal Svagerka, Przemysław Uznański
We consider the problem of computing distance between a pattern of length and all -length subwords of a text in the streaming model. In the streaming setting, only the Hammi…
Lower bounds for text indexing with mismatches and differences
Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length , the "tex…
Streaming dictionary matching with mismatches
Paweł Gawrychowski, Tatiana Starikovskaya
In the -mismatch problem we are given a pattern of length and a text and must find all locations where the Hamming distance between the pattern and the text is at most .…
Fast entropy-bounded string dictionary look-up with mismatches
Paweł Gawrychowski, Gad M. Landau, Tatiana Starikovskaya
We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of strings of length and an integer , we must preprocess it into a dat…
Upper and lower bounds for dynamic data structures on strings
Raphael Clifford, Allan Grønlund, Kasper Green Larsen +1
We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the patte…