19 citations · 110 across the 50 of their papers we have counts for
5 papers · 1 filter
The Power of Distributed Verifiers in Interactive Proofs
Moni Naor, Merav Parter, Eylon Yogev
We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of nodes and a graph that defines their communication pattern…
Low Congestion Cycle Covers and their Applications
Merav Parter, Eylon Yogev
A cycle cover of a bridgeless graph is a collection of simple cycles in such that each edge appears on at least one cycle. The common objective in cycle cover computati…
Congested Clique Algorithms for Graph Spanners
Merav Parter, Eylon Yogev
Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide rang…
Coloring in the Congested Clique Model
Merav Parter
In this paper, we present improved algorithms for the (vertex) coloring problem in the Congested-Clique model of distributed computing. In this model, the input is a graph…
Wireless Expanders
Shirel Attali, Merav Parter, David Peleg +1
This paper introduces an extended notion of expansion suitable for radio networks. A graph is called an -{wireless expander} if for every subset $S \subseteq…