Meirav Zehavi

I am a postdoctoral research fellow at the University of Bergen. My host is Prof. Saket Saurabh. During August 2015 - May 2016, I have been a postdoctoral research fellow at Simons-Berkeley and I-CORE (TAU). My research interests lie in the fields of Kernelization and Parameterized Complexity. 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

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

Articles

2017

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

[28] Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh and Meirav Zehavi. Exact Algorithms for Terrain Guarding.
    - Accepted to the proc. of the 33rd Annual Symposium on Computational Geometry (SoCG 2017). 

[27] Fedor V. Fomin, Daniel Lokshtanov, S.M. Meesum, Saket Saurabh and Meirav Zehavi. Matrix Rigidity: Matrix Theory from the Viewpoint of Parameterized Complexity.
    - Accepted to the proc. of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017). 

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

[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.
    - Conditionally 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.
    - Accepted to Algorithms for Molecular Biology (AMB). (Invited WABI 2016 issue.)

[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 Algorithmica. (Invited CPM 2016 issue.)

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

[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.
    - Conditionally 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.
    - Accepted to SIAM Journal on Discrete Mathematics (SIDMA).

[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.
    - Accepted to Theory of Computing Systems (TOCS).

[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

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


Employment

06/2016 - Current: Postdoctoral Researcher, University of Bergen, Norway
    - Host: Prof. Saket Saurabh
    - Member of the Algorithms Research Group

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


Awards

01/2016 - 12/2017: The Women Postdoctoral Fellowship of Israel's Council for Higher Education.

01/2016 - 05/2016: Simons-Berkeley Research Fellowship.

08/2015 - 12/2015: I-CORE Research Fellowship.

10/2015: Best Student Paper Award at IWOCA'15.

07/2015: Best Student Paper Award at ESA'15.

06/2015: Best Student Paper Award at MFCS'15.

10/2014 - 01/2015: Excellence Scholarship.

03/2014: First prize in the poster competition of 5th CS research day at the Technion.

10/2013 - 09/2014: Zeff Fellowship.

10/2009 - 02/2010 (undergraduate): Departmental scholarship (awarded for developing a bioinformatics tool).


Teaching Assistant

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

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

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

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


Academic Service

Program Committee Member

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

Steering Committee Member

School on Parameterized Algorithms and Complexity in Israel, 2017.

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