Research Interests

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

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 algorithmics), I have touched upon the following:
  • Approximation algorithms in the form of a study of priority algorithms.
  • Algorithmic concurrency issues such as packet routing on a network and shared-memory locking protocols.
  • Hardness of a number of problems, including some related to sports tournaments.
  • Semantic concurrency issues in the form of the first full abstractness results for a non-interleaving denotational semantics for a process languages, as well as some bisimulation model checking work.
  • Regular expressions with back referencing.
  • Bounds for the number of products of affine combinations which can be produced when elements can be arranged freely in matrices, motivated by a technique for improving the communication complexity of zero-knowledge proofs.