5 citations · 21 across the 18 of their papers we have counts for
Showing 2017 · cs.DSShow all
3 papers · 2 filters
cs.DS2017
Superlinear Lower Bounds for Distributed Subgraph Detection
Orr Fischer, Tzlil Gonen, Rotem Oshman
In the distributed subgraph-freeness problem, we are given a graph , and asked to determine whether the network graph contains as a subgraph or not. Subgraph-freeness is an…
cs.DS2017★ 1 cited
On The Multiparty Communication Complexity of Testing Triangle-Freeness
Orr Fischer, Shay Gershtein, Rotem Oshman
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs.…
cs.DS2017★ 4 cited
Distributed Property Testing for Subgraph-Freeness Revisited
Orr Fischer, Tzlil Gonen, Rotem Oshman
In the subgraph-freeness problem, we are given a constant-size graph , and wish to determine whether the network contains as a subgraph or not. The \emph{property-testing} r…