Carmin.tv

Mathematics
and Interactions

Please leave your feedback in order for us to improve your experience !
Not Only Scalar Curvature Seminar
74 videos

Not Only Scalar Curvature Seminar

Geometric structures and discrete group actions / Structures géométriques et actions de groupes discrets
4 videos

Geometric structures and discrete group actions / Structures géométriques et actions de groupes discrets

Misha Gromov : Mathematical Description of Biological Structures
4 videos

Misha Gromov : Mathematical Description of Biological Structures

Applications of NonCommutative Geometry to Gauge Theories, Field Theories, and Quantum Space-Time / Applications de la Géométrie Non Commutative aux Théories de Jauge, à la Théorie des Champs et aux Espaces-Temps Quantiques
5 videos

Applications of NonCommutative Geometry to Gauge Theories, Field Theories, and Quantum Space-Time / Applications de la Géométrie Non Commutative aux Théories de Jauge, à la Théorie des Champs et aux Espaces-Temps Quantiques

All the collections
CIMPA
CIRM
IHES
IHP
LMR
SMF
All the institutions
2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Collection 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Organizer(s) Green Larsen, Kasper ; Hassibi, Babak ; Kerenidis, Iordanis ; Yeung, Raymond
Date(s) 15/02/2016 - 26/02/2016
linked URL https://web.archive.org/web/20221228152146/http://iss.bu.edu/bobak/csnexus//inequalities.html
00:00:00 / 00:00:00
50 51

Tight Cell-probe bounds for Online Hamming distance

By Benjamin Sach

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.

Information about the video

  • Date of publication 14/03/2016
  • Institution IHP
  • Licence CC BY-NC-ND
  • Language English
  • Format MP4

Domain(s)

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Copyright Carmin.tv 2025
By browsing our website, you accept the use of cookies to improve your experience. Find out more about our privacy policy.
Approve
Give feedback