Jan. 13, 2022

Prof. Meirav Zehavi ​of the Department of Computer Science is a recipient of a new European Research Council (ERC) Starting Grant to find a unified solution to path problems. ERC grants, under the new Horizon Europe program, are some of the most prestigious available. The grants provide funding and support for ambitious research.

Prof. Meirav Zehavi and her husband Prof. Klim Efremenko
Prof. Meirav Zehavi and her husband Prof. Klim Efremenko, also of the Department of Computer Science, and a past recipient of an ERC Starting Grant as well.

Modern life is full of computational problems – how do we go (by car, for example) from Point A to Point B using the shortest or longest routes? What is the weekly solution to the crossword or sudoku in the paper?  Given DNA strands from different organisms, how would the “most similar" look and therefore would logically represent a common ancestor? How do we pack items of different sizes optimally into a suitcase or box? On the one hand, unfortunately, most of the computational problems that interest us are “hard" in the sense that it is unlikely (which can be proven under certain assumptions) assuming any hypothetical situation we would encounter, we can find a precise solution in a short amount of time.

On the other hand, luckily, the difficulty can mostly be found in specific parameters of the problem which could be small in reality. For example, on a city map, we can find various routes between places quickly if we use a “tree diagram." A crossword or sudoku could be mostly solved easily using various heuristics like elimination. Regarding DNA strands from different organisms, a precise solution can be found quickly if there are only a few strands or if they are “very similar" to the ones we were given. Regarding packing a suitcase or box, the problem becomes easier if the items only come in a small number of shapes.  

“In my field of research – complexity and parameterized algorithms – we develop tools to identify the parameters that make a problem easier, and develop algorithms which, assuming every situation in which a problem might be encountered, solve them quickly as long as one of the parameters we identified is small. One of the most important topics in the field of complexity and parameterized algorithms, which essentially led to the establishment of the field, are “path problems" of various sorts. In particular, research into these problems have led to many breakthroughs, with important implications for research in other fields, like graph theory, computational geometry, bioinformatics, metroides theory, approximation algorithms, computational economics and choice theory, and more.

“In my research proposal, I explained how I plan on solving some of the most basic problems in this field, some of which have remained open for quite a long time, on the basis of my research findings from the last several years. I presented a unique approach in the sense that I proposed approaching these problems uniformly, something which has not yet been done," explains Prof. Zehavi.

Prof. Zehavi hold MsC and PhD degrees from the Technion - Israel Institute of Technology. She did post-doctoral work at Tel Aviv University, the University of Bergen in Norway and at UC Berkely in California.

She is a recipient of the Alon Fellowship for Outstanding New Faculty and was awarded the Krill Prize for Excellence in Scientific Research.