Summer school
There will be a full-day summer school on July 4.
Jakub Radoszewski (University of Warsaw)
Title: Quasiperiodicity in StringsAn elementary notion that grasps repetitiveness in strings is periodicity. If a string can be generated by repeated concatenation of its smaller piece, then we say that it is periodic. The field of periodicity was generalized by allowing not only concatenation, but also superpositions, which resulted in the introduction of quasiperiodicity. The basic notions of quasiperiodicity are covers and seeds. A cover of a text T is a string whose occurrences in T cover all positions of T, while a seed of T is a cover of some superstring of T.
During the lecture I will present important properties of covers and seeds and show algorithms for computing them, survey other notions of quasiperiodicity (including approximate quasiperiodicity) and known results, and list open problems in this area. The course will also include a tutorial session with exercises on quasiperiodicity.
Martin Farach-Colton (Rutgers University)
Title: Balls, Bins, Hashes, Filters, Stashes, Positive Queries, Negative Queries. And SuccinctnessHashing is one of the most basic data structures. Everyone learns about chaining and a bit about open addressing. Topics such as space-efficient hash tables or constant-time operations are considered advanced. But recent innovations in hash tables has dramatically simplified such “advanced” guarantees. In this tutorial, we will cover recent results in hashing and their implications to such topics as filters. We will cover not only the theoretically best hash tables and filters but the fastest ones in practice. (Spoiler alert: they’re the same ones.)