52 citations · 56 across the 15 of their papers we have counts for
18 papers
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…
Tight Cell-Probe Bounds for Online Hamming Distance Computation
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n…
Pattern Matching in Multiple Streams
Raphael Clifford, Markus Jalsenius, Ely Porat +1
We investigate the problem of deterministic pattern matching in multiple streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The t…
Pattern Matching under Polynomial Transformation
Ayelet Butman, Peter Clifford, Raphael Clifford +5
We consider a class of pattern matching problems where a normalising transformation is applied at every alignment. Normalised pattern matching plays a key role in fields as diverse…