Hi all,
Kristýna is sick, so we have a change of speaker & topic. We will learn simple but powerful methods to hash, presented by Tung.
M.A. Bender, M. Farach-Colton, J. Kuszmaul, W. Kuszmaul: Modern Hashing Made Simple https://epubs.siam.org/doi/pdf/10.1137/1.9781611977936.33
Using standard machinery we construct a simple hash table that offers guarantees much stronger than what are classically taught: • Operations are O(1)-time with high probability; • The hash table stores n k-bit items in nk + O(n log log n) bits of space; • The hash table is dynamically resized, so the space bound holds with respect to the current size n at each time step.
See you all there!
R
-- Robert Šámal IÚUK MFF UK -- CSI of Charles University
On Mon, Nov 11, 2024 at 12:30 PM Robert Samal samal@iuuk.mff.cuni.cz wrote:
Hi all,
Just a reminder: this Thursday we will have the next edition of "doktorandsky seminar". As announced on https://kam.mff.cuni.cz/~dsemweb/, our speaker will be Krystyna Maskova and she will talk about Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum: Delegating Computation: Interactive Proofs for Muggles. J. ACM 62(4): 27:1-27:64 (2015) https://dl.acm.org/doi/10.1145/2699436
Time: Thursday 9:50-12:10 Place: S8
No prerequisites required.
See you there,
R
Robert Šámal IÚUK MFF UK -- CSI of Charles University