Merav Parter
YOU?
Author Swipe
View article: New Oracles and Labeling Schemes for Vertex Cut Queries
New Oracles and Labeling Schemes for Vertex Cut Queries Open
We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected $n$-vertex graph $G = (V,E)$ and integer parameter $f \geq 1$, the goal is supporting vertex cut queries: Given $F \subsete…
View article: A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs
A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs Open
Afek, Bremler-Barr, Kaplan, Cohen, and Merritt (PODC'01) in their seminal work on shortest path restorations demonstrated that after a single edge failure in a graph G, a replacement shortest path between any two vertices s and t, which av…
View article: Distributed Maximum Flow in Planar Graphs
Distributed Maximum Flow in Planar Graphs Open
The dual of a planar graph $G$ is a planar graph $G^*$ that has a vertex for each face of $G$ and an edge for each pair of adjacent faces of $G$. The profound relationship between a planar graph and its dual has been the algorithmic basis …
View article: Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults Open
An $f$-edge (or vertex) connectivity certificate is a sparse subgraph that maintains connectivity under the failure of at most $f$ edges (or vertices). It is well known that any $n$-vertex graph admits an $f$-edge (or vertex) connectivity …
View article: Parks and Recreation: Color Fault-Tolerant Spanners Made Local
Parks and Recreation: Color Fault-Tolerant Spanners Made Local Open
We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to $f$ failures of entire color classes. The failure of even a single color may cause a linear number of individual edge/…
View article: Deterministic Replacement Path Covering
Deterministic Replacement Path Covering Open
In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\su…
View article: Connectivity Labeling and Routing with Multiple Vertex Failures
Connectivity Labeling and Routing with Multiple Vertex Failures Open
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f-vertex/edge fault tolerant (f-V/EFT) connectivity labeling is a scheme that produces succinct labels f…
View article: Component stability in low-space massively parallel computation
Component stability in low-space massively parallel computation Open
In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation ( ) . Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-spac…
View article: Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free Open
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges $F \subseteq G$, the faulty-degree $…
View article: Connectivity Labeling and Routing with Multiple Vertex Failures
Connectivity Labeling and Routing with Multiple Vertex Failures Open
We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An $f$-vertex/edge fault tolerant ($f$-V/EFT) connectivity labeling is a scheme that produces succinct labe…
View article: Distributed CONGEST Algorithms against Mobile Adversaries
Distributed CONGEST Algorithms against Mobile Adversaries Open
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed computation in the presence of mobile adversaries which can dynamically appear throughout the network. Over the years, this setting has been studied m…
View article: Near-Optimal Distributed Computation of Small Vertex Cuts
Near-Optimal Distributed Computation of Small Vertex Cuts Open
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especia…
View article: Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets Open
Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph $G$ is a (small) subset of weighted edges $H$ that when ad…
View article: Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel
Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel Open
We (nearly) settle the time complexity for computing vertex fault-tolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplica…
View article: The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication Open
Theoretical study of optimization problems in wireless communication often deals with tasks that concern a single point. For example, the power control problem requires computing a power assignment guaranteeing that each transmitting stati…
View article: Õptimal Dual Vertex Failure Connectivity Labels
Õptimal Dual Vertex Failure Connectivity Labels Open
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given n-vertex graph G, an f-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each …
View article: Improved Deterministic $(Δ+1)$-Coloring in Low-Space MPC
Improved Deterministic $(Δ+1)$-Coloring in Low-Space MPC Open
We present a deterministic $O(\log \log \log n)$-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of $(Δ+1)$-coloring on $n$-vertex graphs. In this model, every machine has a sublinear local memory o…
View article: Improved Deterministic $(\\Delta+1)$-Coloring in Low-Space MPC
Improved Deterministic $(\\Delta+1)$-Coloring in Low-Space MPC Open
We present a deterministic $O(\\log \\log \\log n)$-round low-space Massively\nParallel Computation (MPC) algorithm for the classical problem of\n$(\\Delta+1)$-coloring on $n$-vertex graphs. In this model, every machine has a\nsublinear lo…
View article: New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $\sqrt{n}$ Barrier
New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $\sqrt{n}$ Barrier Open
For an $n$-vertex digraph $G=(V,E)$, a \emph{shortcut set} is a (small) subset of edges $H$ taken from the transitive closure of $G$ that, when added to $G$ guarantees that the diameter of $G \cup H$ is small. Shortcut sets, introduced by …
View article: Fault-Tolerant Labeling and Compact Routing Schemes
Fault-Tolerant Labeling and Compact Routing Schemes Open
The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as, improved FT routing schemes. For a given $n$-vertex graph $G$ and a bound $f$ on the number of faults, an $f$-FT connectivity labeling scheme is a dist…
View article: Low-Congestion Shortcuts in Constant Diameter Graphs
Low-Congestion Shortcuts in Constant Diameter Graphs Open
Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the congest model of distributed computing. Roughly speaking, for a given graph $G$ and a collection…
View article: Component Stability in Low-Space Massively Parallel Computation
Component Stability in Low-Space Massively Parallel Computation Open
We study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorith…
View article: Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs Open
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two or…
View article: General CONGEST Compilers against Adversarial Edges
General CONGEST Compilers against Adversarial Edges Open
We consider the adversarial CONGEST model of distributed computing in which a fixed number of edges (or nodes) in the graph are controlled by a computationally unbounded adversary that corrupts the computation by sending malicious messages…
View article: Deterministic Replacement Path Covering
Deterministic Replacement Path Covering Open
In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph G, a vertex pair (s, t) ∊ V(G) × V(G), and a set of edge faults F ⊆ E(G), a replacem…
View article: Broadcast CONGEST Algorithms against Adversarial Edges
Broadcast CONGEST Algorithms against Adversarial Edges Open
We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of t edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins…