52 citations · 56 across the 15 of their papers we have counts for
4 papers · 1 filter
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…
Parameterized Matching in the Streaming Model
Markus Jalsenius, Benny Porat, Benjamin Sach
We study the problem of parameterized matching in a stream where we want to output matches between a pattern of length m and the last m symbols of the stream before the next symbol…
Space Lower Bounds for Online Pattern Matching
Raphael Clifford, Markus Jalsenius, Ely Porat +1
We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time…
Tight Cell-Probe Bounds for Online Integer Multiplication and Convolution
Raphael Clifford, Markus Jalsenius
We show tight bounds for both online integer multiplication and convolution in the cell-probe model with word size w. For the multiplication problem, one pair of digits, each from…