Publications

  • Shimon Kogan and Merav Parter
    Giving Some Slack: Shortcuts and Transitive Closure Compressions
    ESA 2024

  • Shimon Kogan and Merav Parter
    The Algorithmic Power of the Greene-Kleitman Theorem
    ESA 2024

  • Merav Parter, Seth Pettie and Asaf Petruschka
    Connectivity Labeling and Routing with Multiple Vertex Failures
    STOC 2024  [arXiv]

  • Greg Bodwin, Bernhard Haeupler and Merav Parter
    Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
    SODA 2024  [arXiv]

  • Merav Parter
    Secure Computation Meets Distributed Universal Optimality
    FOCS 2023

  • Shimon Kogan and Merav Parter
    Towards Bypassing Lower Bounds for Graph Shortcuts
    ESA 2023

  • Shimon Kogan and Merav Parter
    New Additive Emulators
    ICALP 2023

  • Orr Fischer and Merav Parter
    Distributed CONGEST Algorithms against Mobile Adversaries
    PODC 2023 [arXiv]

  • Yael Hitron, Merav Parter and Eylon Yogev
    Secure Distributed Network Optimization Against Eavesdroppers
    ITCS 2023

  • Shimon Kogan and Merav Parter
    Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Cover
    SODA 2023

  • Yael Hitron, Merav Parter and Eylon Yogev
    Broadcast CONGEST Algorithms Against Eavesdroppers
    DISC 2022

  • Merav Parter and Asaf Petruschka
    Near-Optimal Distributed Computation of Small Vertex Cuts
    DISC 2022 [arXiv]

  • Merav Parter and Asaf Petruschka
    \~{O}ptimal Dual Vertex Failure Connectivity Labels 
    DISC 2022 [arXiv]

  • Shimon Kogan and Merav Parter
    Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
    FOCS 2022 [arXiv]

  • Shimon Kogan and Merav Parter
    Beating Matrix Multiplication for $n^{1/3}$-Directed Shortcuts
    ICALP 2022 [Full Version]

  • Merav Parter
    Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time:
    Sequential, Distributed and Parallel

    STOC 2022 [arXiv]

  • Shimon Kogan and Merav Parter
    New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $\sqrt{n}$ Barrier
    SODA 2022 [arXiv]
    Best Paper Award at SODA'22

  • Yael Hitron and Merav Parter
    Broadcast CONGEST Algorithms against Adversarial Edges
    DISC 2021  [arXiv]
    Best Student Paper Award at DISC'21

  • Yael Hitron and Merav Parter
    General CONGEST Compilers against Adversarial Edges
    DISC 2021  [PDF]
    Best Student Paper Award at DISC'21

  • Greg Bodwin and Merav Parter
    Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
    PODC 2021  [arXiv]
    Best Paper Award at PODC'21

  • Michal Dory and Merav Parter
    Fault-Tolerant Labeling and Compact Routing Schemes
    PODC 2021  [arXiv]

  • Shimon Kogan and Merav Parter
    Low-Congestion Shortcuts in Constant Diameter Graphs
    PODC 2021  [arXiv]

  • Artur Czumaj, Peter Davies and Merav Parter
    Improved Deterministic $(\Delta+1)$ Coloring in Low-Space MPC             
    PODC 2021    Full Version 

  • Artur Czumaj, Peter Davies and Merav Parter
    Component Stability in Low-Space Massively Parallel Computation
    PODC 2021   [arXiv]           

  • Karthik C.S. and Merav Parter
    Deterministic Replacement Path Covering
    SODA 2021  [arXiv]

  • Yael Hitron, Cameron Musco and Merav Parter
    Spiking Neural Networks Through the Lens of Streaming Algorithms
    DISC 2020

  • Merav Parter
    Distributed Planar Reachability in Nearly Optimal Time
    DISC 2020

  • Merav Parter
    Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
    DISC 2020

  • Michal Dory and Merav Parter
    Exponentially Faster Shortest Paths in the Congested Clique
    PODC 2020  [arXiv]
    Best Paper Award at PODC'20

  • Artur Czumaj, Peter Davies and Merav Parter
    Simple, Deterministic, Constant-Round Coloring in the Congested Clique
    PODC 2020 [arXiv]

  • Julia Chuzhoy, Merav Parter and Zihan Tan
    On Packing Low-Diameter Spanning Trees
    ICALP 2020 [arXiv]

  • Greg Bodwin, Keerti Choudhary, Merav Parter and Noa Shahar
    New Fault Tolerant Subset Preservers
    ICALP 2020

  • Artur Czumaj, Peter Davies and Merav Parter
    Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
    SPAA 2020 [arXiv]

  • Yael Hitron, Nancy Lynch, Cameron Musco and Merav Parter
    Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks
    ITCS 2020
  • Yael Hitron, Merav Parter and Gur Perri
    The Computational Cost of Asynchronous Neural Communication
    ITCS 2020
  • Uri Ben-Levy and Merav Parter
    New $(\alpha,\beta)$ Spanners and Hopsets
    SODA 2020 [arXiv]
  • Moni Naor, Merav Parter and Eylon Yogev
    The Power of Distributed Verifiers in Interactive Proofs
    SODA 2020 [arXiv]
  • Merav Parter
    Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
    DISC 2019 [arXiv]
  • Yael Hitron and Merav Parter 
    Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons
    ESA 2019 [arXiv]
  • Merav Parter and Eylon Yogev 
    Secure Distributed Computing Made (Nearly) Optimal
    PODC 2019 
  • Merav Parter and Eylon Yogev 
    Optimal Short Cycle Decomposition in Almost Linear Time
    ICALP(A) 2019  [Pdf]
  • Christoph Lenzen, Merav Parter and Eylon Yogev
    Parallel Balanced Allocations: The Heavily Loaded Case
    SPAA 2019 [arXiv]
  • Jason Li and Merav Parter
    Planar Diameter via Metric Compression
    STOC 2019  [arXiv]
  • Merav Parter, Ronitt Rubinfeld, Ali Vakilian and Anak Yodpinyanee
    Local Computation Algorithms for Spanners
    ITCS 2019  [arXiv]
  • Merav Parter and Eylon Yogev 
    Low Congestion Cycle Covers and Their Applications
    SODA 2019  [arXiv]
  • Merav Parter and Eylon Yogev 
    Distributed Computing Made Secure: A Graph Theoreric Approach
    SODA 2019  [arXiv]  [GTACS'18] [My Talk in the Israeli Theory-Day] [Goldreich's Take
  • Merav Parter and Eylon Yogev 
    Congested Clique Algorithms for Graph Spanners
    DISC 2018 [arXiv]
  • Merav Parter and Hsin-Hao Su
    (Delta+1)-Coloring in O(log* Delta) Congested-Clique Rounds
    DISC 2018
  • Shirel Attali, Merav Parter, David Peleg and Shay Solomon
    Wireless Exapnders
    SPAA 2018  [arXiv]
  • Merav Parter
    (Delta+1) Coloring in the Congested Clique Model 
    ICALP(C) 2018  [arXiv]
  • Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter and Guido Proietti 
    Efficient Oracles and Routing Schemes for Replacement Paths 
    STACS 2018  
    [Pdf]
  • Greg Bodwin, Mike Dinitz, Merav Parter and Virginia Vassilevska Williams
    Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
    SODA 2018  [Pdf]
  • Keren Censor-Hillel, Merav Parter and Gregory Schwartsman
    Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
    DISC 2017  [arXiv]
  • Ofer Grossman and Merav Parter
    Improved Deterministic Distributed Construction of Spanners
    DISC 2017  [Pdf]
  • Mohsen Ghaffari and Merav Parter
    Near-Optimal Distributed DFS in Planar Graphs
    DISC 2017  [Pdf]
  • Nancy Lynch, Cameron Musco and Merav Parter
    Neuro-RAM unit with Applications to Similarity Testing and Compression in Spiking Sigmoidal Networks
    DISC 2017  [arXiv] [Slides]
  • Nancy Lynch, Cameron Musco and Merav Parter
    Spiking Neural Networks: An Algorithmic Perspective
    BDA 2017  [Pdf]
  • Greg Bodwin, Fabrizio Grandoni, Merav Parter and Virginia Vassilevska Williams
    Preserving Distances in Very Faulty Graphs
    ICALP(A) 2017  [arXiv]
  • Nancy Lynch, Cameron Musco and Merav Parter
    Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
    ITCS 2017  [Pdf] [MIT News]
  • Mohsen Ghaffari and Merav Parter
    MST in Log-Star Rounds of Congested Clique
    PODC 2016 [Slides] [Pdf]
  • Mohsen Ghaffari and Merav Parter
    A Polylogarithmic Gossip Algorithm for Plurality Consensus
    PODC 2016  [Pdf]
  • Mohsen Ghaffari and Merav Parter
    Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures
    SPAA 2016  [Pdf]
  • Merav Parter, David Peleg and Shay Solomon
    Local-on-Average Distributed Tasks
    SODA 2016  [Pdf]
  • Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
    The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
    FOCS 2015  [Pdf]
  • Keren Censor-Hillel, Erez Kantor, Nancy A. Lynch and Merav Parter
    Computing in Additive Networks with Bounded-Information Codes
    DISC 2015  [Slides] [Pdf]
  • Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
    Nonuniform SINR+Voroni Diagrams Are Effectively Uniform
    DISC 2015  [Slides] [Pdf]
  • Merav Parter and David Peleg
    On the Relations Between SINR Diagrams and Voronoi Diagrams
    ADHOC-NOW (Invited Paper) [Pdf]
  • Merav Parter
    Dual Failure Resilient BFS Structure
    PODC 2015  [Slides] [Pdf]
  • Merav Parter and David Peleg
    Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff
    SPAA 2015  [Slides] [Pdf]
  • Merav Parter
    Vertex Fault Tolerant Additive Spanners
    DISC 2014  [Slides] [Pdf]
    Best Student Paper Award
  • Merav Parter
    Bypassing Erd\H{o}s' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
    ICALP 2014  [Slides] [Pdf]
  • Merav Parter and David Peleg
    Fault Tolerant Approximate BFS Structures
    SODA 2014  [Slides] [Pdf]
  • Michael Dinitz and Merav Parter
    Braess's Paradox in Wireless Networks: The Danger of Improved Technology
    DISC 2013  [Slides] [Pdf]
  • Merav Parter and David Peleg
    Fault-tolerant BFS Trees
    ESA 2013  [Slides] [Pdf]
  • Shiri Chechik, Matthew Johnson, Merav Parter and David Peleg
    Secluded Connectivity Problems
    ESA 2013  [Pdf]
  • Chen Avin, Michael Borokhovich, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
    Generalized Perron--Frobenius Theorem for Multiple Choice Matrices, and Applications
    SODA 2013  [Pdf]
  • Pierre Fraigniaud, Amos Korman, Merav Parter and David Peleg
    Randomized Distributed Decision
    DISC 2012  [Pdf]
  • Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
    SINR Diagram with Interference Cancellation
    SODA 2012  [Slides] [Pdf]
  • Zvi Lotker, Merav Parter, David Peleg and Yvonne Anne Pignolet
    Distributed Power Control in the SINR Model
    INFOCOM 2011  [Pdf]
  • Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
    The Topology of Wireless Communication
    STOC 2011  [Slides] [Video of talk] [Pdf]