19 citations · 110 across the 50 of their papers we have counts for
5 papers · 1 filter
Distributed Interactive Proofs for Planarity with Log-Star Communication
Yuval Gil, Merav Parter
We provide new communication-efficient distributed interactive proofs for planarity. The notion of a \emph{distributed interactive proof (DIP)} was introduced by Kol, Oshman, and S…
All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
Orr Fischer, Merav Parter
Resilient computation in all-to-all-communication models has attracted tremendous attention over the years. Most of these works assume the classical faulty model which restricts th…
New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
Yuval Gil, Merav Parter
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a \emph{distributed interactive proof} (DIP) was introduced by Kol, Oshm…
Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
Merav Parter, Asaf Petruschka
We revisit the problem of fault-tolerant (FT) distance preservers, when failure events in the network admit a form of correlation modeled as color faults. FT distance preservers ar…
New Oracles and Labeling Schemes for Vertex Cut Queries
Yonggang Jiang, Merav Parter, Asaf Petruschka
We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected -vertex graph and integer parameter , t…