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
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
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...