TCS lab mini-course: Gregory Kucherov "Hash-based data structures"
Gregory Kucherov (CNRS/Université Gustave Eiffel, France) invites you to his lectures "Hash-based data structures".
Hash tables are a fundamental technique in software engineering. Beyond this primary application, hash functions have numerous other applications. In these lectures, I will overview several probabilistic data structures relying on hash functions. After summarizing common facts about hashing, we will focus on approximate membership data structures: Bloom filter and Cuckoo filter. Then we will talk about extensions of Bloom filters applied to approximate counting (Count-Min sketch) and computing frequent elements in a stream (heavy hitters). Still in the streaming setting, we will talk about the cardinality estimation problem (a.k.a. count-distinct problem). We will end by a lecture on a special type of hashing increasingly applied in practice: locality-sensitive hashing.
The lectures are oriented to bachelor/master/PhD students with initial background in algorithms and data structures and discrete probability. The lectures can be in english or russian, to be defined with the audience.
Address: Pokrovsky Boulevard 11, R405
Language: English /Russian
Schedule:
24.11.2021 13:00-14:20
24.11.2021 14:40-16:00
25.11.2021 13:00-14:20
25.11.2021 14:40-16:00 additional lecture
To attend the lectures please have your QR-code with you. The lectures will be broadcasted in Zoom.
If you plan to attend either offline or online, please register.