2012/07/08 by Clifford, Raphael, Jalsenius, Markus, Sach, Benjamin
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.2 #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1207.1885
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.