Distributed Computation of Sparse Cuts
Venue: Room No. 007 (LH2), Block A
Time: 11:00 AM, April 11, 2016
Brief Bio of the Speaker:
Anisur Rahaman Molla is currently a postdoc at University of Freiburg, Germany. He studied PhD at Nanyang Technological University, Singapore. He received MTech degree (in Computer Science) from Indian Statistical Institute, Kolkata and BSc, MSc degrees (in Mathematics) from Calcutta University. His research focuses on distributed algorithms and systems.
Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the internet, peer-to-peer networks, web graph, online social communities etc. Sparse cuts are particularly useful in graph clustering among numerous other applications. A sparse cut of a graph is a partition of the vertices into two disjoint subsets such that the ratio between the number of edges crossing the two subsets and the sum of degrees of vertices in the smaller set is minimum. This ratio is known as conductance. In other words, a sparse cut is a cut (i.e., a bi-partition of the vertex set) whose conductance is minimum. In this talk, we will discuss on developing a fast distributed algorithm for computing sparse cuts in undirected graphs. We use random walk as a key subroutine.