BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: The Power of Theory in the Practice of Hashing with
  Focus on Similarity Estimation
DTSTART:20180927T161500
DTEND:20180927T173000
DTSTAMP:20260428T043910Z
UID:35f203d3e6067997eac9a3e3c5cd0341528ea3fc5f400eb3cdd4ce26
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Mikkel Thorup - University of Copenhagen\nVideo of his tal
 k\n\nAbstract: \nHash functions have become ubiquitous tools in modern dat
 a analysis\, e.g.\, the construction of small randomized sketches of large
  data streams. We like to think of abstract hash functions\, assigning ind
 ependent uniformly random hash values to keys\, but in practice\, we have 
 to choose a hash function that only has an element of randomness\, e.g.\, 
 2-independence. While this works for sufficiently random input\, the real 
 world has structured data where such simple hash functions fail\, calling 
 for the need of more powerful hash functions. In this talk\, we focus hash
 ing for set similarity\, which is an integral component in the analysis of
  Big Data. The basic idea is to use the same hash function to do coordinat
 ed sampling from different sets. Depending on the context\, we want subset
 s sampled without replacement\, or fixed-length vectors of samples that ma
 y be with replacement. The latter is used as input to support vector machi
 nes (SVMs) and locality sensitive hashing (LSH). The most efficient constr
 uctions require very powerful hash functions that are also needed for effi
 cient size estimation. We discuss the interplay between the hash functions
  and the algorithms using them. Finally\, we present experiments on both r
 eal and synthetic data where standard 2-independent hashing yield systemat
 ically poor similarity estimates\, while the right theoretical choice is s
 harply concentrated\, and faster than standard cryptographic hash function
 s with no proven guarantees.\n\nBio:\nMikkel Thorup (born 1965) has a D.Ph
 il. from Oxford University from 1993. From 1993 to 1998 he was at the Univ
 ersity of Copenhagen. From 1998 to 2013 he was at AT&T Labs-Research. Sinc
 e 2013 he has been back as Professor at the University of Copenhagen and i
 s now Head of Center for Basic Algorithms Research Copenhagen (BARC) suppo
 rted by the VILLUM Foundation.\n \nMikkel Thorup is a Fellow of the ACM a
 nd of AT&T\, and a Member of the Royal Danish Academy of Sciences and Lett
 ers. He is co-winner of the 2011 MAA Robbins Award and winner of the 2015 
 Villum Kann Rasmussen Award for Technical and Scientific Research\, which 
 is Denmark's biggest individual prize for research. His main work is in al
 gorithms and data structures. One of his best-known early results is a lin
 ear-time algorithm for the single-source shortest paths problem in undirec
 ted graphs.  Recently one of his main focusses has been on hash functions
  unifying theory and practice.\n\nMore information
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR