Meirav Zehavi

News (July): Awarded the Israel Science Foundation (ISF) Individual Research Grant, and the Alon Fellowship for Outstanding Young Faculty. I am looking for excellent postdoctoral/PhD students.

I am an assistant professor (senior lecturer) at the department of Computer Science at Ben-Gurion University, Israel. My research interests lie in the fields of Kernelization and Parameterized Complexity.

Email: zehavimeirav at gmail.com.


Publications

Book

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing.
    - To be published by Cambridge University Press. (~550 pages.)

Survey

Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Some Hard Stable Marriage Problems: A Survey on Multivariate Analysis.
    - To be published in Mathematical Programming and Game Theory (invited).

Peer-Reviewed Articles

2018

[
52] 
Saket Saurabh and Meirav Zehavi. Parameterized Complexity of Multi-Node Hubs. 
    - Accepted to the proc. of 13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

[
51] 
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Polylogarithmic Approximation Algorithms for Weighted F-Deletion Problems. 
    - Accepted to the proc. of the 21th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2018).

[
50] 
Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. When Rigging a Tournament, Let Greediness Blind You.
    - In the proc. of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pages 275-281.

[
49] 
Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Winning a Tournament by Any Means Necessary.
    - In the proc. of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pages 282-288.

[
48] 
Daniel Lokshtanov, M.S. Ramanujan, 
Saket Saurabh and Meirav Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs.
    - In the proc. of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018), pages 135:1-135:14.

[
47] 
Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, 
Saket Saurabh and Meirav Zehavi. 
Long Directed (s,t)-Path: FPT Algorithm.
    - 
Accepted to Information Processing Letters (IPL).

[
46] 
Jayakrishnan Mathadil, 
Saket Saurabh and Meirav Zehavi. 
Max-Cut Above Spanning Tree is Fixed Parameter Tractable.
    - 
In the proc. of the 13th International Computer Science Symposium in Russia (CSR 2018), pages 244-256.
    - Best Paper Award.
    - 
Invited to Theory of Computing Systems (TOCS).

[
45] 
Sushmita Gupta, Fahad Panolan, 
Saket Saurabh and Meirav Zehavi. Stability in Barter Exchange Markets.
    - In the proc. of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), pages 1371-1379.
    - Invited to JAAMAS (Journal of 
Autonomous Agents and Multiagent Systems).

[44] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Erdos-Posa Property of Obstructions to Interval Graphs. 
    - In the proc. of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), pages 7:1-7:15. 

[43] R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi: The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue.
    - In the proc. of the 14th Latin American Theoretical Informatics Symposium (LATIN 2018), pages 712-726.

[42] Gregory Gutin, Felix Reidl, Magnus Wahlstrom and Meirav Zehavi. Designing Deterministic Polynomial Space Algorithms by Color Coding Multivariate Polynomials.
    - In Journal of Computer and System Sciences (JCSS), 2018. Volume 95, pages 69-85.

[41] Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. 
    - In the proc. of the 9th Innovations in Theoretical Computer Science (ITCS 2018), pages 32:1-32:13. 

[40] Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms.
    - In the proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2785-2800. 

[39] Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stephan Thomasse and Meirav Zehavi. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.
    - In the proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 331-342.

[38] Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth.
    - In the proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 262-273.

[37] Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, Ramanujan M. S., Saket Saurabh and Meirav Zehavi. Parameterized Algorithms for Survival Network Design with Uniform Demands. 
    - In the proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2838-2850.

[36] Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Parameterized Algorithms for Deletion to Classes of DAGs.
    - Accepted to Theory of Computing Systems (TOCS).

[35] Deeksha Adil, S
ushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Parameterized Complexity of Stable Matching with Ties and Incomplete Lists.
    - In Theoretical Computer Science (TCS), 2018. Volume 732, pages 1-10.

2017

[34] 
Daniel Lokshtanov, Saket Saurabh,
 
Roohani Sharma 
and Meirav Zehavi. Judicious Partition is FPT.
    In the proc. of 37th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Pages 40:40-40:15.

[33] 
Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Parameterized Analysis for the Group Activity Selection Problem.
    - In the proc. of the 10th International Symposium on Algorithmic Game Theory (SAGT 2017). Pages 106-118.

[32] Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching.
    - In the proc. of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). 
Pages 71:1-71:13.
    - Accepted to Algorithmica.

[31] Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh and Meirav Zehavi. Packing Cycles Faster Than Erdos-Posa.
    - In the proc. of the 44th International Colloquium on Automata, Languages and Programming (ICALP 2017). Pages 71:1-71:15.

[30] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs.
    - In the proc. of the 44th International Colloquium on Automata, Languages and Programming (ICALP 2017). Pages 65:1-65:15.

[29] Christian Komusiewicz, Mateus de Oliveira Oliveira and Meirav Zehavi: Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping.
    - In the proc. of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Pages 11:1-11:17.

[28] Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh and Meirav Zehavi. Exact Algorithms for Terrain Guarding.
    - In the proc. of the 33rd Annual Symposium on Computational Geometry (SoCG 2017).  Pages 11:1-11:15.
    - In ACM Transactions on Algorithms (TALG), 2018. Volume 14(2), pages 25:1-25:20.

[27] Fedor V. Fomin, Daniel Lokshtanov, S.M. Meesum, Saket Saurabh and Meirav Zehavi. Matrix Rigidity: Matrix Theory from the Viewpoint of Parameterized Complexity.
    - In the proc. of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017).  Pages 32:1-32:14.
    - In SIAM Journal on Discrete Mathematics (SIDMA), 2018. Volume 32(2), pages 966-985.

[26] Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Split Contraction: The Untold Story.
    - In the proc. of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017). Pages 5:10-5:14.  

[25] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.
    - In the proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). Pages 1383-1398.  

2016

[24] Fahad Panolan and Meirav Zehavi. Parameterized Algorithms for List K-Cycle.
    In the proc. of the 36th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Pages 22:1-22:15.
    - With Saket Saurabh: Accepted to Algorithmica.

[23] Akanksha Agrawal, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Simlutaneous Feedback Edge Set.
    In the proc. of the 27th International Symposium on Algorithms and Computation (ISAAC 2016). Pages 5:1-5:13.

[22] Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi. Kernels for Deletion to Classes of Acyclic Graphs.
    In the proc. of the 27th International Symposium on Algorithms and Computation (ISAAC 2016). Pages 6:1-5:12.
    - In Journal of Computer and System Sciences (JCSS), 2018. Volume 92, pages 9-21.

[21] Meirav Zehavi: Parameterized Approximation Algorithms for Packing Problems.
    - In Theoretical Computer Science (TCS), 2016. Volume 648, pages 40-55.

[20] Mohammed El-Kebir, Benjamin J. Raphael, Ron Shamir, Roded Sharan, Simone Zaccaria, Meirav Zehavi and Ron Zeira: Copy Number Evolution Problems: Complexity and Algorithms.
    - In the proc. of the 16th Workshop on Algorithms in Bioinformatics (WABI 2016).  Pages 137-149.
    - In Algorithms for Molecular Biology (AMB), 2017. (Invited WABI 2016 issue.) Volume 12(1), pages 13:1-13:11.

[19] Ron Shamir, Meirav Zehavi and Ron Zeira: A Linear-Time Algorithm for the Copy Number Transformation Problem.
    - In the proc. of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Pages 16:1-16:13.
    - In Journal of Computational Biology (JCB), 2017. Volume 12(1), pages 13:1-13:11. 

[18] Meirav Zehavi: A Randomized Algorithm for Long Directed Cycle.
    - In Information Processing Letters (IPL), 2016. Volume 116(6), pages 419-422.

[17] Saket Saurabh and Meirav Zehavi: (k,n-k)-Max Cut: An O*(2^p)-Time Algorithm and a Polynomial Kernel.
    - In the proc. of the 12th Latin American Theoretical Informatics Symposium (LATIN 2016). Pages 686-699.
    - Accepted to Algorithmica.

2015

[16] Meirav Zehavi: The k-Leaf Spanning Tree Problem Admits a Klam Value of 39.
    - In the proc. of the 26th International Workshop on Combinatorial Algorithms (IWOCA 2015). Pages 346-357.
    - Best Student Paper Award.
    - In the European Journal of Combinatorics (EJC), 2018. Volume 68 (IWOCA 2015 invited issue), pages 175-203.

[15] Meirav Zehavi: Mixing Color Coding-Related Techniques.
    In the proc. of the 23rd European Symposium on Algorithms (ESA 2015). Pages 1037-1049.
    - Best Student Paper Award.

[14] Hadas Shachnai and Meirav Zehavi: A Multivariate Framework for Weighted FPT Algorithms.
    In the proc. of the 23rd European Symposium on Algorithms (ESA 2015). Pages 965-976.
    - In Journal of Computer and System Sciences (JCSS), 2017. Volume 89, pages 157-189.

[13] Meirav Zehavi: Maximum Minimal Vertex Cover Parameterized by Vertex Cover.
    - In the proc. of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015). Volume 2, pages 589-600.
    - Best Student Paper Award.
    - Accepted to SIAM Journal on Discrete Mathematics (SIDMA).

[12] Andreas Bjorklund, Vikram Kamat, Lukasz Kowalik and Meirav Zehavi: Spotting Trees with Few Leaves.
    - In the proc. of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015), Track A. Pages 243-255.
    - In SIAM Journal on Discrete Mathematics (SIDMA), 2017. Volume 31(2), pages 687-713.

[11] Prachi Goyal, Neeldhara Misra, Fahad Panolan and Meirav Zehavi: Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets.
    - In SIAM Journal on Discrete Mathematics (SIDMA), 2015. Volume 29(4), pages 1815-1836.

2014

[10] Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi: Improved Parameterized Algorithms for Network Query Problems.
    - In the proc. of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014). Pages 85-96.

[9] Ran Ben-Basat, Ariel Gabizon and Meirav Zehavi: The k-Distinct Language: Parameterized Automata Constructions.
    - In the proc. of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014). Pages 294-306.
    - In Theoretical Computer Science (TCS), 2016. Volume 622, pages 1-15.

[8] Hadas Shachnai and Meirav Zehavi: Representative Families: A Unified Tradeoff-Based Approach.
    In the proc. of the 22nd European Symposium on Algorithms (ESA 2014). Pages 786-797.
    - In Journal of Computer and System Sciences (JCSS), 2016. Volume 82(3), pages 488-502.

[7] Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi: Deterministic Parameterized Algorithms for the Graph Motif Problem.
    - In the proc. of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014). Volume 2, pages 589-600.
    - In Discrete Applied Mathematics (DAM), 2016. Volume 213, pages 162-178.

[6] Hadas Shachnai and Meirav Zehavi: Parameterized Algorithms for Graph Partitioning Problems.
    - In the proc. of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014). Pages 384-395.
    - In Theory of Computing Systems (TOCS), 2017. Volume 61(3), pages 721-738.

[5] Ron Y. Pinter and Meirav Zehavi: Algorithms for Topology-Free and Alignment Network Queries.
    - In Journal of Discrete Algorithms (JDA), 2014. Volume 27, pages 29-53.

[4] Meirav Zehavi: An Improved k-Exclusion Algorithm.
    - In Journal of Computers (JCP), 2014. Volume 9, pages 529-536.

2013 (MSc)

[3] Meirav Zehavi: Algorithms for k-Internal Out-Branching and k-Tree in Bounded Degree Graphs.
    - In the proc. of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013). Pages 361-373.
    - In Algorithmica, 2017. Volume 78(1), pages 319-341.

[2] Meirav Zehavi: Parameterized Algorithms for Module Motif.
    - In the proc. of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013). Pages 825-836.
    - In Information and Computation, 2016. Volume 251, pages 179-193.

[1] Ron Y. Pinter and Meirav Zehavi: Partial Information Network Queries.
    - In the proc. of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013). Pages 362-375.
    - With Hadas Shachnai: In Journal of Discrete Algorithms (JDA), 2015. Volume 31 (invited IWOCA 2013 issue), pages 129-145.

Technical Report (Unpublished)

Dor Ganor, 
Ron Y. Pinter and Meirav Zehavi. GRegNetSim: A Tool for the Discrete Simulation and Analysis of Genetic Regulatory Networks.
    - Technical Report CS-2017-03 (cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2017/CS/CS-2017-03).
    - Project undertaken during my BSc studies; awarded an internal departmental fellowship.


Grant

10/2018 - 09/2022: Israel Science Foundation (ISF) individual research grant (grant no. 1176/18).


Postdoctoral Researchers

Siddharth Gupta, Supported by the Zuckerman Postdoctoral Scholarship for High-Achieving Scholars from Premier Universities in the United States, Will join on 10/2018


Students

Roni Zoller, MSc Student (co-advised with Prof. Michal Ziv-Ukelson), 03/2018-Present

Guy Saar, MSc Student, 03/2018-Present


Employment

10/2017 - Current: Assistant Professor, Ben-Gurion University of the Negev, Israel
    - Fellowship: Awarded the Alon Fellowship for Outstanding Young Faculty

06/2016 - 09/2017: Postdoctoral Researcher, University of Bergen, Norway
    - Member of the Algorithms Research Group, Hosted by Prof. Saket Saurabh
    - Fellowship: Awarded the Women Postdoctoral Fellowship of Israel's Council for Higher Education

01/2016 - 05/2016: Postdoctoral Researcher, University of California, Berkeley
    - Fellowship: Awarded the Simons-Berkeley Research Fellowship

08/2015 - 12/2015: Research Intern/Postdoctoral Researcher, Tel Aviv University, Israel
    - Fellowship: Awarded the I-CORE in Algorithms Research Fellowship


Education

09/2015: PhD in Computer Science, Technion
    - Advisors: Prof. Ron Y. Pinter and Prof. Hadas Shachnai
    - Dissertation title: Algorithms for Parameterized Graph Problems with Applications to Biological Network Queries
    - Fellowships: Awarded the Zeff Fellowship and the Excellence Fellowship

03/2013: MSc in Computer Science, Technion
    - Advisor: Prof. Ron Y. Pinter
    - GPA: 96.44


Teaching

- 03/2018 - 09/2018 (1 semester): Topics in Parameterized Complexity (20214571, Undergraduate+Graduate), Ben-Gurion University

- 10/2017 - 03/2018 (1 semester): Parameterized Algorithms (20226191, Undergraduate+Graduate), Ben-Gurion University

- 10/2014 - 03/2015 (1 semester): Approximation Algorithms (236521, Undergraduate+Graduate), Technion

- 10/2010 - 09/2014 (8 semesters, in parallel to 3): File Systems (234322, Undergraduate), Technion

- 03/2012 - 09/2012, 03/2014 - 09/2014 (2 semesters, in parallel to 2): Project in Bioinformatics (236524, Undergraduate+Graduate), Technion

- 10/2009 - 09/2010 (2 semesters): Introduction to Computer Science (234114, Undergraduate), Technion


Academic Service

Program Committee Member

- The 13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

- The 13th International Computer Science Symposium in Russia (CSR 2018).

- The 11th International Symposium on Parameterized and Exact Computation (IPEC 2016).

Organizer

New Horizons in Parameterized Compexity, Schloss Dagstuhl Seminar 43-011, Jan. 20-25, 2019, Dagstuhl,
Germany.

Recent Advances in Parameterized Complexity (Workshop), December 3-7, 2017, Tel-Aviv, Israel. See rapctelaviv.weebly.com/.

Rangoli of Algorithms (RoA 2016, Workshop), December 11-12, 2016, Chennai, India. See roa2016.weebly.com/.

Invited Talks at Workshops

Invited talk at the minisymposium "Modification Problems to Discrete Structures" at University of Colorado Denver, USA, June 4 - June 8, 2018. See siam.org/meetings/dm18/.

- Invited tutorial at the event ``The Parameterized Complexity Summer School'' in Vienna, Austria, Sep. 1 - Sep. 3, 2017. See algo2017.ac.tuwien.ac.at/pcss/.

- Invited talk at the celebration of Michael R. Fellows' 65th birthday at the University of Bergen, Norway, June 15 - June 16, 2017. See www.ii.uib.no/~mike65/.

- Invited tutorial at Dagstuhl Seminar 17041,``Randomization in Parameterized Complexity'' at Schloss Dagstuhl, Germany, Jan. 22 - Jan. 27, 2017. See www.dagstuhl.de/en/program/calendar/semhp/?semnr=17041.

- Invited talk at the meeting ``BioCS16: Mini-Meeting on the Computer Science/Biology Interface'' at the Institute of Mathematical Sciences, Chennai, India, Dec. 10 - Dec. 11, 2016. See www.imsc.res.in/ rsidd/biocs2016/.

- Invited talk at the workshop ``The Bergen-Kiel Workshop'' at the University of Bergen, Norway, Nov. 24, 2016.

Invited talk at the workshop "NMI Thematic Workshop on Complexity Theory" at IIT Gandhinagar, India, Nov. 4 - Nov. 6, 2016. See sites.iitgn.ac.in/events/2016/nmi/.

Invited talk at the minisymposium "Parameterized Algorithms and Graph Decompositions" at Georgia State University, USA, June 6 - June 10, 2016. See siam.org/meetings/dm16/.

Invited talk at the workshop "Computational Cancer Biology" at Berkeley, USA, Feb. 1 - Feb. 5, 2016. A video is available at simons.berkeley.edu/talks/meirav-zehavi-02-02-2016.

Invited  talk at the workshop "Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms" at Berkeley, USA, Nov. 2 - Nov. 6, 2015. A video is available at simons.berkeley.edu/talks/meirav-zehavi-2015-11-05.

Invited talk at the workshop "At the Interface of Biology and Computation" at the Technion, Israel, Jan. 6, 2014. See cs.technion.ac.il/news/2013/657/docs/pinter.pdf.