Showing cs.DSShow all
2 papers · 1 filter
cs.DS2014
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…
cs.DS2014
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…