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.

Over the latest few years, we have focused on advice complexity. Here, one considers an information theoretical approach to the lack of knowledge of the future when processing input online as opposed to offline. For instance, one can explore how many bits of oracle advice it is sufficient for an online algorithm to consult in order to match an offline algorithm. Or one can determine how many bits of information are necessary for an algorithm to beat the lower bound on the competitive ratio of any (or the best known) online algorithm.

A recent interest is online algorithms with predictions. This is similar to using advice, except that the predictions are not necessarily accurate. The predictions could for example come from a machine learning component. The goal is to design algorithms that are optimal when predictions are perfect, and degrade gracefully with deteriorating predictions until it meets the guarantees provided by an online algorithm.

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: