Department of Computer Science @ Purdue University

Gopal Pandurangan

Assistant Professor of Computer Science

Address

    Purdue University
    Department of Computer Science
    305 N. University Street
    West Lafayette, Indiana, 47907-2107
    Office Phone: +1 765-494-0916
    FAX:          +1 765-494-0739

Research

My research interests are in algorithms, distributed computing, communication networks (especially ad hoc wireless and sensor networks and peer-to-peer networks), energy-efficient computing, and computational biology. I am interested in the theory, algorithms, modeling, and design issues in distributed and large-scale networks.

Selected Research Contributions

M. Khan and G. Pandurangan. A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, Distributed Computing, vol. 20, 2008, 391-402. One of the four invited papers selected by the DISC program committee that appeared in the special issue dedicated to DISC 20th anniversary. DISC Archives - Outstanding Papers. Journal link. pdf. Preliminary version in 20th International Symposium on Distributed Computing (DISC), 2006. Best Student Paper Award. LNCS 4167, Springer-Verlag, 2006. A webstory on this paper . This paper gives the first efficient distributed approximation algorithm for the minimum spanning tree problem, one of the most fundamental problems in distributed computing.

A. Das Sarma, D. Nanongkai, and G. Pandurangan. Fast Distributed Random Walks, Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2009. pdf. Random walks in networks are a fundamental tool in many network applications. This paper presents the first non-trivial distributed algorithms for performing random walks that are significantly faster than existing approaches.

M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2008. pdf. This paper gives a uniform approach to design distributed approximation algorithms for fundamental network optimization problems including the generalized Steiner forest (a generalization of the minimum Steiner tree) and the shortest paths problem. These are widely used primitives in distributed communication networks. This paper also contains the best leader election (one of the two basic problems of distributed computing, the other being consensus) algorithm known: the algorithm is simultaneously both time optimal and (almost) message optimal (in synchronous networks). This addresses an open problem posed by David Peleg in 1990.

M. Khan, G. Pandurangan, and V.S.A. Kumar. Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, 20(1), 2009, 124-139. journal link. pdf

Y. Choi, M. Khan, V.S. Anil Kumar, and G. Pandurangan. Energy-Optimal Distributed Algorithms for Minimum Spanning Trees, IEEE Journal on Selected Areas in Communications, Issue on Stochastic Geometry and Random Graphs in Wireless Networks, 27(7), Sept. 2009. pdf. These two papers initiate a distributed algorithmic theory that uses energy complexity as a new performance measure to analyze distributed algorithms in wireless communication networks. They gives energy-efficient distributed algorithms for the fundamental minimum spanning tree problem in wireless networks.

J. Chen and G. Pandurangan. Almost-Optimal Gossip-Based Aggregate Computation, submitted. pdf.

J. Chen, G. Pandurangan, and D. Xu. Robust Aggregates Computation in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis, in IEEE Transactions on Parallel and Distributed Systems, 17(9), 2006. pdf. Preliminary version in Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), 2005. These two papers give efficient algorithms for computation of aggregates (such as MAX, MIN, SUM, AVG, etc.) in networks, a key problem. The first paper gives the best-known gossip-based algorithms in the point-to-point model. The second gives efficient algorithms in a wireless network model.

A. Ferrante, G. Pandurangan, and K. Park. On the Hardness of Optimization in Power-Law Graphs, Theoretical Computer Science, vol. 393, 2008, 220-230. pdf. This work addresses a fundamental problem: understanding the algorithmic complexity of important combinatorial optimization problems in realistic models of power-law graphs --- a class of graphs widely used to model large-scale real-world networks such as the Web, Internet, peer-to-peer, social, and biological networks. It is shown that many classical NP-hard graph-theoretic optimization problems remain NP-hard on simple power-law graphs. This is the first work that initiates a systematic study of complexity of combinatorial optimization in power-law graphs and has important implications to its modeling and optimization aspects of real-world graphs.

G. Pandurangan and G. Park. Analysis of Randomized Protocols for Conflict-Free Distributed Access, Algorithmica, vol. 49, Number 2 / October, 2007. full text at journal website, pdf. Preliminary version in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2005. In many distributed settings data and resources are shared and there are constraints on their simultaneous access by participating nodes. A fundamental goal in such a setting is to design local distributed contention-resolution protocols so that all the competing nodes can access the shared resources in a coordinated manner. In this paper, we study the following distributed access problem which naturally arises in many settings: given a set of data items shared among nodes in a distributed network, all nodes want to access all (or a subset of) the items residing on different nodes in a contention-free manner. The goal is to design distributed protocols so that all nodes access all the desired items as quickly as possible, while not overloading the storage space of any one processor. We analyze a simple and natural, randomized, distributed contention-resolution protocol and show that it performs almost as well as an optimal (centralized) scheme but with no coordination overhead.

G. Pandurangan and E. Upfal. Entropy-based Bounds for Online Algorithms, ACM Transactions on Algorithms, 3(1), Feb., 2007. pdf. Preliminary version in SODA , 2001 This paper gives a novel information-theoretic approach (based on entropy) to characterize performance of online algorithms that is different from the standard competitive analysis.We characterize performance of classical online problems such as prefetching, caching, and list accessing. These entropy-based bounds have been shown to be useful in understanding the performance of online algorithms in real applications: Fonseca et al. use our bounds to explain the strong correlation between entropy and the performance of LRU algorithm in Web caches.

S. Muthukrishnan and G. Pandurangan. The Bin-Covering Technique for Thresholding Random Geometric Graph Properties, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005. pdf This paper introduces a technique called bin covering to determine the thresholds of important properties of random geometric graphs. This technique shows a way to obtain precise thresholds in a unified and simple manner.

G. Pandurangan, P. Raghavan, and E. Upfal. Using PageRank to Characterize Web Structure, Internet Mathematics, 3(1), 2006, 1-20. postscript, pdf. This paper develops new and more accurate models of the World Wide Web based on the PageRank distribution. This work has been extensively cited (over 120 citations in Google Scholar) and in several books including the textbook by Baldi et al (used as a text in a course in UC Irvine): Modeling the Internet and the Web. The paper is also cited in the recent popular books: Search Engine Society and The Myth of Digital Democracy.

G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks, IEEE Journal on Selected Areas in Communications (JSAC), Issue on Internet and WWW Measurement, Mapping, and Modeling, 21(6), Aug. 2003, 995-1002. postscript, pdf. Preliminary version in Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2001. This paper gives a provably efficient protocol for distributed construction of connected, low-diameter P2P networks. This was the first P2P protocol with provable guarantees on connectivity and diameter under a realistic dynamic setting. This paper has over 200 citations in Google Scholar and cited in many books on P2P. Our protocol has been implemented as part of the Information Visualization CyberInfrastructure (IVC) software framework at Indiana university.

C. Bailey-Kellog, S. Chainraj, and G. Pandurangan. A Random Graph Approach to NMR Sequential Assignment, Journal of Computational Biology, Vol. 12, No.6-7, 2005, 569-583. pdf. Invited paper. Preliminary version in 8th Annual International Conference on Research in Computational Biology (RECOMB), 2004. This paper addresses a fundamental algorithmic problem in protein structure determination via NMR. It gives provably efficient algorithms that also work well in practice.

G. Pandurangan and H. Ramesh. The Restriction Mapping Problem Revisited, Journal of Computer and System Sciences, 65, 2002, 526-544. Invited paper for a special issue in Computational Biology. postscript, pdf This paper tackles the classical restriction mapping problem in computational biology and gives the first-known polynomial algorithm for it. Also gives an efficient algorithm for de novo peptide sequencing.

Publications by Date

Publications by Category

A (Partial) List at DBLP

Research Description

Lab

Network Algorithms and Analysis Laboratory (NAAL)

Ph.D. Students

Dr. Maleq Khan : Graduated in Aug. 2007. Currently Post-doc at the Network Dynamics and Simulation Science Laboratory, VBI, Virginia Tech.
Dissertation: Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems with Applications to Wireless Ad Hoc Networks.

Dr. Jen-Yeu Chen : Graduated in Dec. 2007. Co-advised with Prof. Hu (ECE). Currently Assistant Professor of Electrical Engineering at National Dong Hwa University, Taiwan.
Dissertation: Distributed Randomized Algorithms for Robust Aggregate Computation in Wireless Sensor Networks.

Vasil Denchev.

The Mathematics Genealogy Project

Selected Talks

Energy-efficient Distributed Algorithms for Wireless Ad hoc Networks . The IEEE 22nd Annual Computer Communications Workshop (CCW), 2008, Steamboat Springs, CO.

Efficient Distributed Approximation Algorithms. Presented at Microsoft Research (India), Indian Institute of Science, Bangalore, and University of Illinois at Urbana Champaign, 2008.

Efficient Distributed Approximation Algorithms for Minimum Spanning Trees. Presented at Harvard University, Carnegie-Mellon University, Brown University, Dartmouth College, Ohio State University, SUNY Albany, Indian Institute of Science, Indiana University-Purdue University (IUPUI), Microsoft Research (Silicon Valley, USA and Bangalore, India), and Bell Labs, India, 2007.

Complexity of Combinatorial Optimization in Power-Law Graphs, Invited talk at the SIAM Conference on Discrete Mathematics, 2006.

A Random Graph Approach to Protein Structure Determination , DIMACS Workshop on Biomolecular Networks, DIMACS Center, Rutgers University, 2005.

Entropy-based Bounds for Online Algorithms, Invited talk at the 38th Annual Conference on Information Sciences and Systems(CISS), Princeton University, NJ, 2004.

Random Graphs in Peer-to-Peer Networks 2nd Bertinoro Workshop on Random(ized) Graphs and Algorithms , Bertinoro, Italy, 2003, and 9th Seminar on the Analysis of Algorithms , San Miniato-Pisa, Italy, 2003.

Protocols for Building Low-Diameter P2P Networks, DIMACS Workshop on Internet and WWW Measurement, Mapping and Modeling, Rutgers University, NJ, 2002.