Siddhartha Brahma will present his research seminar/general exam on Wednesday May 23 at 10AM in Room 402. The members of his committee are Bob Tarjan (advisor), Moses Charikar, and Boaz Barak. 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. ------------------------------- Abstract: Studies in Distribution Sensitive Data Structures A distribution senstitve 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 stuctures (eg. planar point location data sturctures, priority queues, etc). We will give a broad survey of the whole area, mentioning some recent results in detail and discuss some interesting open problems. We will also show some preliminary results for data structures for the Max Priority Interval problem having some of the properties described above. 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 SoCG 2003. [6] R. E. Tarjan. Amortized computational complexity. SIAM J. Appl. Discrete Meth., 1983. [6] Dion Harmon. New Bounds on Optimal Binary Search Trees. PhD thesis, MIT, Boston, MA, 2006. [7] M. T. Goodrich, M. Orletsky, K. Ramaiyer, Methods for achieving fast query times in point location data structures, in SODA 1997. [8] Data Structures and Network Algorithms. Robert E. Tarjan, 1983. [9] John Iacono: Optimal planar point location. SODA 2001. [10] Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu: Dynamic Optimality -- Almost. FOCS 2004. [11] C.C.Wang, J.Derryberry, D.D.Sleator: O(\log\log n)-competitive dynamic binary search trees. SODA 2006.