The Taub Faculty of Computer Science Events and Talks

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