News/blog Contact

Research Interests

As brief as possible, this ordered list of (overlapping) areas characterize my interests:
Online Algorithms, Data Structures, Database Systems, Algorithms.
A slightly more detailed description is given below, and some impression can be obtained by checking my publication list, list of students, list of courses, or full cv.

Online Algorithms

My primary interest has been performance measures, including the accommodating function, relative worst order analysis, and advice complexity, but also classic competitive analysis and other measures. Along the way, I have worked with many concrete online problems, including bin packing call control, coloring, inventory management, k-server, list accessing, packet bundling (dynamic TCP acknowledgment), paging, scheduling, seat reservation, streaming, and unit clustering. I have considered many variations of these problems, including fair and unfair variants, dual versions, etc. A recent interest is online algorithms with advice.

Data Structures

Most of my work in this area has dealt with search trees with relaxed balance, involving variants of B-trees, AVL-trees, red-black trees, and other structures. I have also looked at chronological transcript operations in persistent search trees as well as various amortized analysis issues.

Database Systems

My work on search trees with relaxed balance came out of a database index motivation. I have also worked on smooth incorporation of grouping and domain value computation in relational algebra and on various query optimization issues, limiting the need for sorting of temporary results.


In addition to the problems areas above (most of which fall under the headline of algorithms), I have touched upon the following: