Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme
Organisateur(s)
Date(s)
19/05/2024
Tight Cell-probe bounds for Online Hamming distance
We give a tight cell-probe bound for the time to compute Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. The task is to output the Hamming distance between a fixed n-dimensional vector and a vector of the n most recent values from a stream. One symbol of the stream arrives at a time and the each output must be computed before the next symbols arrives. In this talk we will give a lower bound of Ω((δ/(w+loglogn))logn) time on average per output, where δ is the number of bits needed to represent an input symbol and w is the cell or word size (which may be as small as a single bit). We will also argue that this is bound is in fact tight within the cell probe model.
