7 citations · 26 across the 14 of their papers we have counts for
15 papers
The k-mismatch problem revisited
Raphaël Clifford, Allyx Fontaine, Ely Porat +2
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and ev…
Dictionary matching in a stream
Raphael Clifford, Allyx Fontaine, Ely Porat +2
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report…
The complexity of computation in bit streams
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We revisit the complexity of online computation in the cell probe model. We consider a class of problems where we are first given a fixed pattern or vector of symbols and t…
Time Bounds for Streaming Problems
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational mo…
Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of symbo…
Fingerprints in Compressed Strings
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a d…