Arrow Research search

Author name cluster

Markus Jalsenius

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers
2 author rows

Possible papers

4

SODA Conference 2013 Conference Paper

Tight Cell-Probe Bounds for Online Hamming Distance Computation

  • Raphaël 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 and the last n symbols of a stream. We give a lower bound of time on average per output, where δ is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. The lower bound holds under randomisation and amortisation.

Details