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