Siddhartha Brahma will present his research seminar/general exam on Monday January 7 at 2PM in room 402. The members of his committee are: Robert Tarjan (advisor), Moses Charikar, and Sanjeev Arora. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Distribution Sensitive Data Structures A distribution sensitive data structure is one whose running time on a sequence of operations supported by the data structure depends on some distributional properties of the sequence. Although some work had been done before, distribution sensitive data structures became important after the seminal paper on Splay trees by Sleator and Tarjan[0]. In the paper several types of distributive properties were defined and it was proved that splay trees have several of these properties (eg. static optimality, working set property, dynamic finger property, etc) by using amortized analysis, and miraculously without storing any extra information about the sequence. Then the question naturally arises whether we can define similar properties for data structures other than binary search trees. There has been interesting work recently in terms of both defining new properties (unified property) and proving these properties for new or existing data structures (eg. planar point location data structures, priority queues, etc). We will start off with a broad survey of the whole area. Then we will prove several results for the working set data structure extending it to work for predecessor queries and improving the insertion and deletion times. We will also look at an extension of splay trees called Multi-Splay trees that has been recently proposed. We will prove new results on the amortized time to perform joins and splits on Multi-Splay trees. Reading List: [0] D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J.ACM, 1985. [1] John Iacono. Distribution Sensitive Data Structures. Ph.D. Thesis. Rutgers, SUNY,2001. [2] Chengwen Chris Wang. Multi-Splay Trees. PhD thesis, CMU, Pittsburg, PA, 2006. [3] Introduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press, 2001.(Chapters 10-14, 17, 18-21) [5] J.Iacono and S.Langerman. Proximate planar point location. in SODA 2003 [6] R. E. Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth., 1983. [7] Data Structures and Network Algorithms. Robert E. Tarjan, 1983 [8] John Iacono: Optimal planar point location. SODA 2001 [9] Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality--Almost. FOCS 2004 [10] C.C.Wang, J.Derryberry, D.D.Sleator: O(\log\log n)-competitive dynamic binary search trees. SODA 2006 [11] Heather D. Booth. An overview of Red-Black and Finger Trees. Technical Report. Princeton University, 1990.