| Title | : | A Distributed Conductance Testing Algorithm |
| Speaker | : | Yadu Vasudev (IITM) |
| Details | : | Fri, 24 Nov, 2017 3:00 PM @ A M 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 bounded-degree 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. |
