[talks] S Brahma general exam

[Melissa M Lawson]

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.