The School of Computing and Mathematical Sciences, Algorithms Group Seminar.
When:
—
Venue:
Birkbeck Main Building, Malet Street
Speaker: Tugkan Batu
Title: Distributed Conductance Testing
Abstract:
In this talk, I will present a simple and time-optimal distributed algorithm for property testing a graph on $n$ vertices for its conductance in the CONGEST model. Our algorithm takes only $O(\log n)$ rounds of communication (which is known to be optimal), and consists of simply running multiple random walks of $O(\log n)$ length from a number of random vertices, at the end of which nodes can decide if the underlying graph is a good conductor or far from one. The algorithm generates $O(m^2)$ walks, where $m$ is the number of edges in the graph. Unlike previous algorithms, no aggregation of information is required. Our main technical contribution involves a tight analysis of this process using spectral graph theory. We introduce and leverage the concept of sticky vertices which are vertices in a graph with low conductance such that short random walks originating from these vertices end in a region around them.
Joint work with Amitabh Trehan and Chhaya Trehan.
Contact name:
Oded Lachish