History Independence in Data Structures

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence has a rich history of study as a security guarantee, with the intent being to minimize risks incurred by a breach or audit. In recent work, history independence has also been used as an algorithmic tool, by hiding information from an oblivious adversary in order to produce faster data structures. In this talk, I will present examples of my work in both of these applications of history independence in data structures, followed by some questions of interest for future work.