MZ Meirav ZehaviHead of Parameterized Analysis Laboratory

Full Professor · Stein Faculty of Computer and Information Science · Ben-Gurion University

Meirav Zehavi

Head of Parameterized Analysis Laboratory

Last updated: 18 June, 2026

Meirav Zehavi
150+publications 2books ERC, ISF & BSFresearch grants 60+program committees 20students and postdocs
Research Areas

My research is centered on Parameterized Analysis, connecting its methods and perspectives with a broad range of areas across computer science.

Theory and algorithmic techniques for preprocessing computational problems with provable guarantees.

Exact, FPT, and lower-bound results for graph problems, with emphasis on width measures, graph minors, and sparse structures.

Geometric intersection graphs, crossing minimization, guarding, packing, and graph drawing.

Tournament manipulation, stable matchings, voting, fair division, and participatory budgeting.

Decision-tree learning, interpretability, reconfiguration problems, and robot motion planning.

Approximation schemes, lossy preprocessing, FPT approximation, parameterized streaming, and parameterized counting.

Biological network queries, phylogeny, gene clusters, genome rearrangements and copy-number evolution.

Books
Forthcoming book for children
Cover of Hochmat Haalgorithmicaim Hachadasha

Hochmat Haalgorithmicaim Hachadasha

Zehavi, M.

Cinnamon Publishing

~350 pages; expected late 2026 / early 2027.

Research monograph
Cover of Kernelization: Theory of Parameterized Preprocessing

Kernelization: Theory of Parameterized Preprocessing

Fomin, F.V.; Lokshtanov, D.; Saurabh, S.; Zehavi, M.

Cambridge University Press

>500 pages; published in 2019.

Active grants
07/2022–06/2027

Parameterized Complexity Through the Lens of Path Problems

European Research Council (ERC) Starting Grant

1,499,821 EUR

Grant no. 101039913; five years.

10/2024–09/2028

Parameterized Problems on Geometric Graphs

Israel Science Foundation (ISF) individual research grant

880,000 NIS

Grant no. 1470/24; four years.

Browse the full list of grants
Honors
  • BGU Vice President Award for Ground-breaking Research
  • Toronto Prize for Excellence in Research
  • Krill Prize for Excellence in Scientific Research
  • Alon Fellowship for Outstanding New Faculty in Israel
  • PC Chair of STACS 2027 and IPEC 2021
  • Keynote Speaker of SoCG 2025 and GD 2021
  • Editorial Board Member of Six Journals, including TheoretiCS and ACM TALG
Browse the full list of honors
Recent selected publications
S12026Survey

Parameterized Algorithms on Geometric Intersection Graphs

Xue, J., Zehavi, M.

Computer Science Review, vol. 58, no. 100796.

22026STOC

Fine-Grained Bounds for Courcelle’s Theorem

Lokshtanov, D., Panolan, F., Saurabh, S., Xue, J., Zehavi, M.

Proc. of the 58th Annual ACM Symposium on Theory of Computing (STOC’26), pp. 2254–2265.

42026SODA

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization

Fomin, F.V., Golovach, P., Inamdar, T., Saurabh, S., Zehavi, M.

Proc. of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’26), pp. 4628–4643.

122025STOC

Subexponential Parameterized Algorithms for Hitting Subgraphs

Lokshtanov, D., Panolan, F., Saurabh, S., Xue, J., Zehavi, M.

Proc. of the 57th Annual ACM Symposium on Theory of Computing (STOC’25), pp. 1975-1984.

132025STOC

Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs

Lokshtanov, D., Panolan, F., Saurabh, S., Xue, J., Zehavi, M.

Proc. of the 57th Annual ACM Symposium on Theory of Computing (STOC’25), pp. 1965–1974.

172025SODA

Crossing Number in Slightly Superexponential Time

Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., Xue, J., Zehavi, M.

Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’25), pp. 1412–1424.

92025ICML

What Makes an Ensemble Hard to Interpret? A Theoretical Approach

Bassan, S., Amir, G., Zehavi, M., Katz, G.

Proc. of the 42nd International Conference on Machine Learning (ICML’25).

82025EC

Tournament Robustness via Redundancy

Efremenko, K., Molter, H., Zehavi, M.

Proc. of the 26th ACM Conference on Economics and Computation (EC’25), pp. 66–85.

142025AAAI

Adaptive Manipulation for Coalitions in Knockout Tournaments

Chaudhary, J., Molter, H., Zehavi, M.

Proc. of the 39th AAAI Conference on Artificial Intelligence (AAAI’25), pp. 13700–13708.

Browse the full publication list