Scholars 2020

Tel Aviv University, Department of Computer Science 

"Design & Analysis of Data Structure/Algorithmic Issues (IP networks) / Algorithmic & Molecular Biology"

January 2006
My research is in theoretical computer science. More specifically on algorithms and data structures. I have been working on algorithmic problems related to several application areas such as networking, string matching, and computational geometry. I have been supervised seven graduate students with whom I have published many papers.

With my student Nira Shafrir and colleges I have been working on string matching problem. We have been making considerable progress on the shortest superstring problem, and now we work on finding approximate tandem repeats which have applications in computational molecular biology.

Much of my recent research has been focused on algorithmic problems in computational geometry. Together with students and Prof. Micha Sharir we have developed several kinetic data structures to maintain configurations of moving objects.

Specifically we suggest algorithms to maintain the closest pair of a set of moving points, and the convex hull of a set of moving points. I also developed with Prof. Sharir online algorithms for conflict free coloring, and techniques for approximate range counting.

I have also made basic research on fundamental questions on data structures, such as the boolean union-find problem and the meldable heap data type.

I intend to continue this line of research on algorithms and data structures, in string matching geometry and other application areas. I intend to use the geometric intuitions that I have accumulated to attack several other open problems on geometric data structures and geometric sampling techniques. Among others we are currently working on generalized range searching problems where the objects are classified to different types. Other algorithmic application area that I an involved in is algorithmic game theory and analysis of the performance of equilibria.