b'Merav Parter'

research

∙ 09/13/2023

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

We study a new and stronger notion of fault-tolerant graph structures wh...

0 Greg Bodwin, et al. ∙

research

∙ 07/12/2023

Connectivity Labeling for Multiple Vertex Failures

We present an efficient labeling scheme for answering connectivity queri...

0 Merav Parter, et al. ∙

research

∙ 05/23/2023

Distributed CONGEST Algorithms against Mobile Adversaries

In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the stud...

0 Orr Fischer, et al. ∙

research

∙ 11/17/2022

Near-Optimal Distributed Computation of Small Vertex Cuts

We present near-optimal algorithms for detecting small vertex cuts in th...

0 Merav Parter, et al. ∙

research

∙ 11/13/2022

Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets

Hopsets and spanners are fundamental graph structures, playing a key rol...

0 Shimon Kogan, et al. ∙

research

∙ 09/07/2022

Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel

We (nearly) settle the time complexity for computing vertex fault-tolera...

0 Merav Parter, et al. ∙

research

∙ 08/22/2022

Õptimal Dual Vertex Failure Connectivity Labels

In this paper we present succinct labeling schemes for supporting connec...

0 Merav Parter, et al. ∙

research

∙ 12/10/2021

Improved Deterministic (Δ+1)-Coloring in Low-Space MPC

We present a deterministic O(logloglog n)-round low-space Massively Para...

0 Artur Czumaj, et al. ∙

research

∙ 11/25/2021

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the √(n) Barrier

For an n-vertex digraph G=(V,E), a shortcut set is a (small) subset of e...

0 Shimon Kogan, et al. ∙

research

∙ 06/03/2021

Low-Congestion Shortcuts in Constant Diameter Graphs

Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016...

0 Shimon Kogan, et al. ∙

research

∙ 06/03/2021

Component Stability in Low-Space Massively Parallel Computation

We study the power and limitations of component-stable algorithms in the...

0 Artur Czumaj, et al. ∙

research

∙ 06/01/2021

Fault-Tolerant Labeling and Compact Routing Schemes

The paper presents fault-tolerant (FT) labeling schemes for general grap...

0 Michal Dory, et al. ∙

research

∙ 02/19/2021

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs

The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt ...

0 Greg Bodwin, et al. ∙

research

∙ 10/04/2020

Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers

Fault tolerant distance preservers (spanners) are sparse subgraphs that ...

0 Merav Parter, et al. ∙

research

∙ 10/03/2020

Spiking Neural Networks Through the Lens of Streaming Algorithms

We initiate the study of biological neural networks from the perspective...

0 Yael Hitron, et al. ∙

research

∙ 09/13/2020

Simple, Deterministic, Constant-Round Coloring in the Congested Clique

We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring p...

0 Artur Czumaj, et al. ∙

research

∙ 08/12/2020

Deterministic Replacement Path Covering

In this article, we provide a unified and simplified approach to derando...

0 Karthik C. S., et al. ∙

research

∙ 06/12/2020

On Packing Low-Diameter Spanning Trees

Edge connectivity of a graph is one of the most fundamental graph-theore...

0 Julia Chuzhoy, et al. ∙

research

∙ 04/14/2020

Round-Efficient Distributed Byzantine Computation

We present the first round efficient algorithms for several fundamental ...

0 Yael Hitron, et al. ∙

research

∙ 03/06/2020

Exponentially Faster Shortest Paths in the Congested Clique

We present improved deterministic algorithms for approximating shortest ...

0 Michal Dory, et al. ∙

research

∙ 12/24/2019

Planar Diameter via Metric Compression

We develop a new approach for distributed distance computation in planar...

0 Jason Li, et al. ∙

research

∙ 12/11/2019

Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

The Massively Parallel Computation (MPC) model is an emerging model whic...

0 Artur Czumaj, et al. ∙

research

∙ 08/08/2019

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

We revisit classical connectivity problems in the CONGEST model of distr...

0 Merav Parter, et al. ∙

research

∙ 07/26/2019

New (α,β) Spanners and Hopsets

An f(d)-spanner of an unweighted n-vertex graph G=(V,E) is a subgraph H ...

0 Uri Ben-Levy, et al. ∙

research

∙ 04/25/2019

Winner-Take-All Computation in Spiking Neural Networks

In this work we study biological neural networks from an algorithmic per...

0 Nancy Lynch, et al. ∙

research

∙ 04/16/2019

Parallel Balanced Allocations: The Heavily Loaded Case

We study parallel algorithms for the classical balls-into-bins problem, ...

0 Christoph Lenzen, et al. ∙

research

∙ 02/27/2019

Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons

We consider the task of measuring time with probabilistic threshold gate...

0 Yael Hitron, et al. ∙

research

∙ 02/21/2019

Local Computation Algorithms for Spanners

A graph spanner is a fundamental graph structure that faithfully preserv...

0 Merav Parter, et al. ∙

research

∙ 12/28/2018

The Power of Distributed Verifiers in Interactive Proofs

We explore the power of interactive proofs with a distributed verifier. ...

0 Moni Naor, et al. ∙

research

∙ 12/09/2018

Low Congestion Cycle Covers and their Applications

A cycle cover of a bridgeless graph G is a collection of simple cycles i...

0 Merav Parter, et al. ∙

research

∙ 05/14/2018

Congested Clique Algorithms for Graph Spanners

Graph spanners are sparse subgraphs that faithfully preserve the distanc...

0 Merav Parter, et al. ∙

research

∙ 05/07/2018

(Δ+1) Coloring in the Congested Clique Model

In this paper, we present improved algorithms for the (Δ+1) (vertex) col...

0 Merav Parter, et al. ∙

research

∙ 02/20/2018

Wireless Expanders

This paper introduces an extended notion of expansion suitable for radio...

0 Shirel Attali, et al. ∙

research

∙ 12/04/2017

Distributed Computing Made Secure: A New Cycle Cover Theorem

In the area of distributed graph algorithms a number of network's entiti...

0 Merav Parter, et al. ∙

research

∙ 06/05/2017

Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks

We study distributed algorithms implemented in a simplified biologically...

0 Nancy Lynch, et al. ∙

research

∙ 10/06/2016

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks

We initiate a line of investigation into biological neural networks from...

0 Nancy Lynch, et al. ∙

Merav Parter

Featured Co-authors