Search Mailing List Archives
[theory-seminar] Theory Lunch 10/29: Søren Dahlgaard on Tabulation-Based Hashing
Dan Michael Stubbs
dstubbs at stanford.edu
Tue Oct 27 11:59:51 PDT 2015
Like most weeks, this week has a Thursday, and school will be in session, so let's have lunch and theory. The speaker will be Søren Dahlgaard, who is visiting from the University of Copenhagen, and will tell us about tabulation-based hashing.
Food will be available starting around 12:15pm, and the talk starts at 12:30pm, in 463A, the fourth floor B wing lobby/conference room.
Hope to see you there!
The power of tabulation-based hashing
Randomized algorithms are often enjoyed for their simplicity, however the hash
functions needed to yield the desired theoretical guarantees are often
complicated or impractical. In the recent years a surge of research has gone
into analyzing tabulation-based hashing schemes. These schemes provide simple
and very efficient implementations with very powerful properties.
Tabulation-based hashing dates back to Zobrist in 1970 and was also considered
by Carter and Wegman [STOC'77]. In a breakthrough paper Patrascu and Thorup
[STOC'11] analyzed the simplest possible tabulation scheme and showed that this
provided strong guarantees for several applications such as Cuckoo hashing,
minwise hashing, linear probing, etc. Following their paper, a long line of research
have shown very strong results for both simple tabulation and similar
tabulation-based hashing schemes, see e.g. Thorup [FOCS'13], Patrascu and
Thorup [SODA'13], Dahlgaard et. al [FOCS'15], Dahlgaard et. al [SODA'16]. It
should be noted that Thorup and Zhang [SODA'04,SICOMP'12] had already
considered tabulation-based hashing in the context of second moment estimation
and linear probing.
Tabulation-based hashing is a perfect example of what we often desire in
research: Simple algorithms with complicated analysis (since simple algorithms
with simple analysis are often uninteresting). In this talk I will survey the
field of tabulation-based hashing and explain the basic methods used for
proving theorems. I will discuss several state-of-the-art results retaining to
k-partition, uniform hashing, bloom filters, constant moment bounds and the
power of two choices.
Joint work with:
Mathias Bæk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar