Speaker: Daniel Golovin Time: Wednesday 12-1pm Location : NSH 1305 Title : Strongly History Independent Hashing Abstract : We present the first strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. A hash table that supports deletion is SHI if it has a canonical memory representation up to randomness. That is, the string of random bits and current hash table contents (the set of (key, object) pairs in the hash table) uniquely determine its layout in memory, independently of the sequence of operations from initialization to the current state. Thus, the memory representation of a SHI hash table reveals exactly the information available through the hash table interface, and nothing more. Our SHI hash table stores n objects of equal size in O(n) slots of space, where a slot is enough space to store a (key, object) pair, and executes insertions, deletions, and searches in expected O(1) time. Other Information: This is joint work with Guy Blelloch. This talk is intended for a general CS audience.