Talk by Ioana Bercea on Locally Uniform Hashing

On August 25, 2025, 13:15-14:15, we are happy to host a talk by Ioana Bercea on Locally Uniform Hashing. The talk will take place in Erzherzog-Johann-Platz 1, 1040 Wien, in Seminarraum FB 02 10 (second floor). You are most welcome to join us.

Title: Locally Uniform Hashing

Speaker: Ioana Bercea, KTH Royal Institute of Technology

Abstract: Hashing is a commonly used technique for getting improved algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity.

About: Ioana is an Assistant Professor at KTH Royal Institute of Technology. Prior to that, shw was a Postdoc in the Basic Algorithms Research Copenhagen (BARC) group at the IT University of Copenhagen, hosted by Prof. Thore Husfeldt. Before joining BARC, she was a Postdoc at Tel Aviv University, hosted by Prof. Guy Even. Ioana obtained her PhD in Computer Science from the University of Maryland, where she was advised by Prof. Samir Khuller. Her research interests are in the broad area of Theoretical Computer Science and specifically in data structures, randomized and approximation algorithms, and computational geometry.