Invited Talk by Dr. Anisur Rahaman on Distributed Computation of Sparse Cuts

Title: Distributed Computation of Sparse Cuts
Speaker: Dr. Anisur Rahaman
Host Faculty: Dr.Sathya Peri
Room No: LH2, 007
Time: 11:00

Abstract:

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.

Speaker’s Bio:

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.

For more information, visit his webpage:https://sites.google.com/site/mollaanisurrahaman

Dates:
Monday, April 11, 2016 - 11:00