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

Guy Even - COLLOQUIUM LECTURE

Tuesday, 19.12.2017, 14:30

Room 337 Taub Bld.

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:
Guy Even received his B.Sc. degree in 1988 in Mathematics and Computer
Science from the Hebrew University. Received his M.Sc. and D.Sc. in
Computer Science from the Technion in 1991 and 1994,
respectively. Dr. Even spent his post-doctorate in the University of
the Saarland during 1995–1997 with Prof. Wolfgang Paul. Since 1997, he
is a faculty member in the School of Electrical Engineering in
Tel-Aviv University. Dr. Even is interested in algorithms and their
applications in various fields. He has published papers on the theory
of VLSI, approximation algorithms, computer arithmetic, online
algorithms, frequency assignment, scheduling, packet-routing,
linear-programming decoding of LDPC codes, and rateless codes. He is
on the editorial board of "Theory of Computing Systems". Together
with Moti Medina, Dr. Even wrote a digital hardware textbook titled
"Digital Logic Design: A Rigorous Approach" published in 2012 by
Cambridge University Press.
=============================================
Refreshments will be served from 14:15
Lecture starts at 14:30