Tight Cell-probe bounds for Online Hamming distance

49 views · Published 14 March 2016 · 47:37 · Indexed 12 November 2026

Channel: Institut Henri Poincaré · 2016 · Science & Technology

Watch on YouTube

By Benjamin Sach (University of Bristol
Abstract: 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 [Math Processing Error]-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 [Math Processing Error] time on average per output, where [Math Processing Error] is the number of bits needed to represent an input symbol and [Math Processing Error] 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.

More from this channel