  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 Omega((d/w)*log n) time on average per output, where d 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.
