DEPARTMENT SEMINAR 

Daniel Golovin
Carnegie Mellon University
Department of Computer Science

Monday, March 3, 2008
Computer Science Building, Room 151
4:00 PM

Faculty Host: Ramesh Sitaraman

"Uniquely Represented Data Structures with Applications to Privacy"

A uniquely represented data structure has a unique physical state to
encode each logical state of its abstract data type. 
In this talk I will discuss new efficient uniquely represented
versions of popular data structures (including hash tables, binary
search trees, and queues), how these data structures work, and how
they can be used to improve the security and privacy of real-world
applications. 

As an example application, consider a typical system with some
internal data structures. If the memory representations of those
internal data structures are inspected, they may leave significant
clues to the past use of the system. For example, a data structure
with lazy deletions might retain an object that the user believes was
deleted long ago; this is problematic in environments requiring high
security or strict privacy guarantees. Uniquely represented data
structures eliminate such problems entirely by storing exactly the
information specified by an abstract data type, and nothing more. 

Short Bio:

Daniel Golovin is a Ph.D. candidate at Carnegie Mellon University
under the supervision of Guy Blelloch. His research interests include
approximation and online algorithms, using novel data structures to
improve privacy, and provably good ways of dealing with
uncertainty. He received his B.S. from Cornell University in 2003 and
his M.S. from Carnegie Mellon University in 2006. 

Refreshments at 3:45 PM in the atrium, outside the presentation room.