Faster and Simpler Distributed CONGEST-Algorithms for Testing and Correcting Graph Properties

Tuesday, 19.12.2017, 14:30
Room 337 Taub Bld.
Dept. of Electrical Engineering-Systems, Tel-Aviv University
Yuval Filmus

We consider the following problem introduced by [Censor-Hillel et al., DISC 2016]. Design a distributed algorithm (called an $\epsilon$-tester) that tests whether the network over which the algorithm is running satisfies a given property (e.g., acyclic, bipartite) or is $\epsilon$-far from satisfying the property. If the network satisfies the property, then all processors must accept. If the network is $\epsilon$-far from satisfying the property, then (with probability at least $2/3$) at least one processor must reject. Being $\epsilon$-far from a property means that at least $\epsilon\cdot |E|$ edges need to be deleted or inserted to satisfy the property. Suppose we have an $\epsilon$-tester that runs in $O(Diameter)$ rounds. We show how to transform this tester to an $\epsilon$-tester that runs in $O((\log |V|)/\epsilon))$ rounds. Since cycle-freeness and bipartiteness are easily tested in $O(Diameter)$ rounds, we obtain $\epsilon$-testers for these properties with a logarithmic number of rounds. Moreover, for cycle-freeness, we obtain a \emph{corrector} of the graph that locally corrects the graph so that the corrected graph is acyclic. The corrector deletes at most $\epsilon \cdot |E| + distance(G,P)$ edges and requires $O((\log |V|)/\epsilon))$ rounds. Joint work with Reut Levy and Moti Medina. Short Bio: ========== ============================================= Refreshments will be served from 14:15 Lecture starts at 14:30

Back to the index of events