BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T122124Z
UID:Seminar-dept-1274@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250520T140000
DTEND:20250520T150000
SUMMARY:School Seminar Series
DESCRIPTION:Andrew Krapivin: Optimal Bounds for Open Addressing Without Reordering\n\nIn this talk, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper ``Uniform Hashing is Optimal''. All of our results come with matching lower bounds.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1274
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR