Title  :  A Distributed Conductance Testing Algorithm 


Speaker  :  Yadu Vasudev
(IIT Madras) 

Details  :  Thu, Nov 23, 2017 3:00 PM, @ Turing Hall 


Abstract  :  We study property testing problems in the distributed CONGEST model. In particular, we look at the problem of testing whether a graph has conductance at least $Phi$ or is $epsilon$far from having conductance at least $Phi^2$ in the CONGEST model. In the classical property testing model, there is a algorithm for testing conductance of boundeddegree graphs with query complexity $sqrt{n}$. We show that for graphs with arbitrary degree there is an $O(log n)$ round algorithm for testing algorithm in the CONGEST model. In fact, we show that the algorithm works even when the size of the graph is not known apriori. We also prove a matching lower bound for the problem. 