[talks] S Brahma general exam

[Melissa M Lawson]

 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.