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.

Algorithms

In addition to the problems areas above (most of which fall under the headline of algorithms), 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, sorting networks, and query optimization.
• 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.
• Optimization problems in flight planning involving A*-inspired algorithm and geometric issues.
• Synthesis planning in a DNA-templated context.
• Efficient implementation of choreography extraction.