Meirav Zehavi

Last update: 27.10.2017.

Recent Advances in Parameterized Complexity will be held on December 3-7, 2017 in Tel Aviv, Israel. Please visit rapctelaviv.weebly.com to register.

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

During June 2016 - October 2017, I have been a postdoctoral research fellow at the University of Bergen, where I was fortunate to be hosted by Prof. Saket Saurabh. During August 2015 - May 2016, I have been a postdoctoral research fellow at Simons-Berkeley and I-CORE (TAU), where I was hosted by Prof. Ron Shamir. I obtained my PhD from the Technion in September 2015, under the supervision of Prof. Ron Y. Pinter and Prof. Hadas Shachnai, and I obtained my MSc from the Technion in March 2013, under the supervision of Prof. Ron Y. Pinter.

Email: zehavimeirav at gmail.com.


Publications

Book

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

Survey

[41] 
Sushmita Gupta, Sanjukta Roy, 
Saket Saurabh and Meirav Zehavi. Some Hard Stable Marriage Problems: A Survey on Multivariate Analysis.
    - Invited to a research monograph.

Articles

2018

[40] Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. 
    - Accepted to the proc. of the 9th Innovations in Theoretical Computer Science (ITCS 2018). 

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

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

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

[36] 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. 
    - Accepted to the proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

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

2017

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

[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.
    - Accepted to the proc. of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).

[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.

[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.

[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.

[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.
    - Accepted to Journal of Computer and System Sciences (JCSS).

[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.
    - Accepted to Journal of Computational Biology (JCB).

[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.
    - Accepted to the European Journal of Combinatorics (EJC). (IWOCA 2015 invited issue.)

[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

[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.


Education

09/2015: PhD in Computer Science, Technion
    - Advisors: Prof. Ron Y. Pinter and Prof. Hadas Shachnai
    - Topic: Parameterized Complexity
    - 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
    - Topic: Bioinformatics
    - GPA: 96.44


Employment

10/2017 - Current: Assistant Professor, Ben-Gurion University, Israel

06/2016 - 09/2017: Postdoctoral Researcher, University of Bergen, Norway
    - Host: Prof. Saket Saurabh
    - Member of the Algorithms Research Group
    - 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


Teaching

- 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).

Steering Committee Member

School on Parameterized Algorithms and Complexity in Israel, 2017. See rapctelaviv.weebly.com/.

The 1st Workshop on Rangoli of Algorithms (RoA 2016). See roa2016.weebly.com/.

Invited Talks at Workshops

- 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.