Faculty Candidate 2014

Distributed Computing and Large-scale Graph Processing: Foundations and Applications

When: Friday, March 7, 2014
Where: Agnes Hall (AH) 108
Time: 11:00 AM

Speaker: Gopal Pandurangan, Brown University and Nanyang Technological University

Host: Prof. Carlos Ordonez

A distributed network consists of a set of processors that communicate by message passing via an underlying communication network. Distributed algorithms have been studied extensively for over three decades.

In the first part of the talk, we will focus on two quintessential problems --- minimum spanning tree (MST) and random walk sampling --- and present our recent results that establish tight time bounds for both problems.

In the second part of the talk, we will focus on distributed processing of  large-scale graph data which has  become very important with the emergence of ``Big Graph Data" in the form of the Web graph, social networks, biological networks etc. Recent graph processing systems such as Pregel and Giraph can do computation on graphs having billions of nodes.  These systems use a message-passing ``vertex-centric" computation model that mimics the distributed network computation model. We show that algorithms for distributed network computing can be leveraged to obtain efficient large-scale graph algorithms. We present tight bounds for several fundamental graph  problems including MST and PageRank. 

Bio:
Prof. Gopal Pandurangan (http://www.ntu.edu.sg/home/gopal) is affiliated with the Theoretical Computer Science research group in the Mathematical Sciences Division at Nanyang Technological University. He is currently a research fellow at the Institute of Experimental and Computational Research in Mathematics (ICERM) at Brown University and also a visiting faculty in the Computer Science Department at Brown University. He received his Ph.D. from Brown University (2002), Masters from SUNY Albany, and B.Tech. from IIT Madras, all in Computer Science. He is a senior member of the ACM and the IEEE. His research interests are in the design and analysis of algorithms, distributed computing, large-scale data processing, communication networks, real-world networks, and computational biology.