| Title | : | Distributed Property Testing Algorithms |
| Speaker | : | Yadu Vasudev (TU Dortmund, Germany) |
| Details | : | Thu, 15 Dec, 2016 2:30 PM @ BSB 361 |
| Abstract: | : | We study property testing algorithms in the distributed CONGEST model. We show how to leverage the parallelism in the model to design fast distributed algorithms for testing various graph properties. In the dense graph model we show how to simulate the sequential tests for nearly all graph properties having 1-sided tests in the distributed CONGEST model. In the sparse graph model we give fast algorithms for various graph properties, improving the bounds given by the standard property testing algorithms. We also obtain nearly tight lower bounds in the LOCAL model for cycle-freeness testing and bipartiteness testing. We will also look at some open questions and new research directions. Speaker Bio : Dr. Yadu Vasudev is currently a postdoctoral fellow at TU Dortmund, Germany. Prior to this, he was a postdoctoral fellow at Technion-Israel Institute of Technology, Haifa and obtained his PhD from The Institute of Mathematical Sciences (IMSc) Chennai in July 2014. His research interests are in Algorithms, specifically sublinear algorithms, Computational Complexity theory, Graph Isomorphism problem. |
