The following is a list of all publications in reverse chronological order. Copies of most works are available for download.
Please send me mail if you find something missing.
G. Pandurangan. Energy-Efficient Distributed Algorithms, Department of Computer Science, University of New Mexico, and Department of Computer Science and Engineering, IIT Madras, 2022.
G. Pandurangan. Fully-Distributed Byzantine Protocols in Peer-to-Peer Networks, Workshop on Blockchains and Networking, ACM SIGMETRICS, 2022.
J. Augustine, A.R. Molla, and G. Pandurangan. Byzantine Agreement and Leader Election: From the Classical to the Modern, Tutorial, PODC 2021,and ICDCN 2020.
G. Pandurangan. Fast Byzantine Agreement and Leader Election in Dynamic Networks, Workshop on Security of Permissionless Systems (co-located with PODC 2019), 2019, Toronto, Canada (Invited Speaker).
G. Pandurangan. Agreement and Leader Election in a Distributed World, VAJRA lecture, IIT Madras, 2018.
G. Pandurangan, P. Robinson, and M. Scquizzato. The Distributed Minimum Spanning Tree Problem, EATCS Bulletin, No. 125, June 2018. pdf
G. Pandurangan. Distributed Algorithmic Foundations of Large-Scale Data Computation, Tutorial, Department of Computer Science, IIT Madras, 2018.
G. Pandurangan. Distributed Algorithmic Foundations of Large-Scale Data Computation, Invited Talk, Department of Computer Science, Texas A&M University, 2017.
G. Pandurangan. Distributed Computation of Large-Scale Graph Problems, Distinguished Speaker, Parallel and Distributed Systems Lab, Dept. of ECE, UT Austin, 2016.
G. Pandurangan. Distributed Computation of Large-Scale Graph Problems, Theory of Distributed Systems Seminar, MIT, 2016.
G. Pandurangan. Distributed Algorithmic Foundations of Dynamic Networks, ACM SIGACT News, 47(1), March 2016, 69-98. pdf
G. Pandurangan. Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks, FOCS 2015.
G. Pandurangan. Distributed Computation of Large-Scale Graph Problems, SODA 2015.
G. Pandurangan. Distributed Computing and Large-scale Graph Processing: Foundations and Connections, NII Shonan Workshop on Large-scale Graph Algorithms, Shonan Japan, 2014.
G. Pandurangan. Distributed Algorithmic Foundations of Dynamic Networks (with Churn), Invited Talk, 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO) July 23 - 25, 2014, Hida Takayama, Japan, 2014.
G. Pandurangan. Distributed Algorithmic Foundations of Dynamic Networks, Invited Talk, 4th Singapore Mathematics Symposium, 2013, and Stochastic Graph Models Workshop, ICERM, Brown University.
G. Pandurangan. Network Discovery via Gossip: Analyzing Dynamically Evolving Distributed and Social Networks, Invited Talk, ACM PODC Social Network Workshop, 2013, and Invited Colloquium talk, Department of Statistics, National University of Singapore, 2013.
A. Das Sarma, G. Pandurangan, and D. Nanongkai. Efficient Distributed Random Walk Computation and Applications, Invited Tutorial, 14th International Conference on Distributed Computing and Networking (ICDCN), 2013.
G. Pandurangan. How Fast Can You Compute in a Distributed Network ? Presented at IIT Chennai and Indian Institute of Science, Bangalore, 2011. (Focuses on proving lower bounds for fundamental distributed computing problems.)
G. Pandurangan and M. Khan. Theory of Communication Networks, Invited Book Chapter in Algorithms and Theory of Computation Handbook, Second Edition, M.J. Atallah and M. Blanton (Editors), CRC Press, 2009. pdf. (Focuses on the theoretical and algorithmic underpinnings of today's wide-area communication networks, especially the Internet.)
V. Denchev and G. Pandurangan. Distributed Quantum Computing: A New Frontier in Distributed Systems or Science Fiction?, ACM SIGACT News, 39(3), September 2008, 77-95. pdf. SIGACT News distributed computing column.
G. Pandurangan. Energy-efficient Distributed Algorithms for Wireless Ad hoc Networks. The IEEE 22nd Annual Computer Communications Workshop (CCW), 2008, Steamboat Springs, CO.
G. Pandurangan. Efficient Distributed Approximation Algorithms, Presented at Microsoft Research (India), Indian Institute of Science, Bangalore, and University of Illinois at Urbana Champaign, 2008. (Focuses on algorithms for fundamental distributed computing problems.)
G. Pandurangan. 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.
G. Pandurangan. Complexity of Combinatorial Optimization in Power-Law Graphs, Invited talk at the SIAM Conference on Discrete Mathematics, 2006.
G. Pandurangan. A Random Graph Approach to Protein Structure Determination, DIMACS Workshop on Biomolecular Networks, DIMACS Center, Rutgers University, 2005.
G. Pandurangan. 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.
G. Pandurangan. Protocols for Building Low-Diameter P2P Networks, DIMACS Workshop on Internet and WWW Measurement, Mapping and Modeling, Rutgers University, NJ, 2002.
Fabien Dufoulon, Frederic Magniez, Gopal Pandurangan. Quantum Communication Advantage for Leader Election and Agreement. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2025.
Fabien Dufoulon and Gopal Pandurangan. Improved Byzantine Agreement under an Adaptive Adversary. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2025. Best Paper Award.
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram Pemmaraju, and Peter Robinson. Message Optimality and Message-Time Trade-offs for APSP and Beyond. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2025.
Dominic Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Tom Hayes, Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2025 (Brief announcement).
John Augustine, Fabien Dufoulon, and Gopal Pandurangan. Fully-Distributed Byzantine Agreement in Sparse Networks, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. arxiv.org/abs/2410.20865
Fabien Dufoulon, Gopal Pandurangan, Peter Robinson, Michele Scquizzato. The Singular Optimality of Distributed Computation in LOCAL. Proceedings of the Conference on Principles of Distributed Systems (OPODIS), 2024. arxiv.org/abs/2411.07011
Khalid Hourani, William K. Moses Jr., and Gopal Pandurangan. Towards Communication-Efficient Peer-to-Peer Networks, Proceedings of the European Symposium on Algorithms (ESA), 2024. https://arxiv.org/abs/2406.16661
John Augustine, William K. Moses Jr., and Gopal Pandurangan. Awake Complexity of Distributed Minimum Spanning Tree. Proceedings of the 31st International Colloquium On Structural Information and Communication Complexity (SIROCCO), 2024. https://arxiv.org/abs/2204.08385
Fabien Dufoulon, Michael Moorman, William K. Moses Jr., and Gopal Pandurangan. Time- and Communication-Efficient Overlay Network Construction via Gossip, Proceedings of the Innovations in Theoretical Computer Science (ITCS), 2024. https://arxiv.org/abs/2311.17115
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. The Message Complexity of Distributed Graph Optimization, Proceedings of the Innovations in Theoretical Computer Science (ITCS), 2024. https://arxiv.org/abs/2311.14811
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan. Distributed MIS in O(log log n) Awake Complexity, Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2023. Invited to the Distributed Computing Journal special issue of the best papers of PODC 2023. https://arxiv.org/pdf/2204.08359.pdf
Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm, Proceedings of the 36th International Symposium on Distributed Computing (DISC) 2022. https://drops.dagstuhl.de/opus/volltexte/2022/17210/
J. Augustine, A. Molla, G. Pandurangan, Y. Vasudev. Byzantine Connectivity Testing in the Congested Clique, Proceedings of the 36th International Symposium on Distributed Computing (DISC) 2022. https://drops.dagstuhl.de/opus/volltexte/2022/17198/
J. Augustine, S. Chatterjee, and G. Pandurangan. A Fully-Distributed Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022.
K. Hourani, G. Pandurangan, and P. Robinson. Awake-Efficient Distributed Algorithms for Maximal Independent Set, 42nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2022 (Poster). https://ieeexplore.ieee.org/document/9912131
S. Chatterjee, G. Pandurangan, and P. Robinson. Byzantine-Resilient Counting in Networks. 42nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2022.
Eric Ajieren, Khalid Hourani, William K. Moses Jr., and Gopal Pandurangan. Distributed Algorithms for Connectivity and MST in Large Graphs with Efficient Local Computation. 23rd International Conference on Distributed Computing and Networking (ICDCN), 2022.
Shreyas Pai, Gopal Pandurangan, Sriram Pemmaraju, and Peter Robinson. Can We Break Symmetry with o(m) Communication? 40th ACM Symposium on Principles of Distributed Computing (PODC), 2021. https://arxiv.org/abs/2105.08917
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Near Optimal Leader Election in Asynchronous Networks, Proceedings of the 35th International Symposium on Distributed Computing (DISC) 2021. https://drops.dagstuhl.de/opus/volltexte/2021/14829/
John Augustine, Kishore Kothapalli, and Gopal Pandurangan. Efficient Distributed Algorithms in the k-machine Model via PRAM Simulations, 35th International Parallel and Distributed Processing Symposium (IPDPS), 2021.
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols, 34th International Symposium on Distributed Computing (DISC), 2020. pdf
Shay Kutten, William Moses, Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election 34th International Symposium on Distributed Computing (DISC), 2020. https://arxiv.org/abs/2008.02782
S. Chatterjee, R. Gmyr, and G. Pandurangan. Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity, 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020. https://arxiv.org/abs/2006.07449
S. Gilbert, G. Pandurangan, P. Robinson, A. Trehan. DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead, 39th ACM Symposium on Principles of Distributed Computing(PODC), 2020. pdf
R. Fathi, Anisur Rahaman Molla, and G. Pandurangan. Efficient Distributed Algorithms for the K-Nearest Neighbors Problem, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020. (Brief Announcement) Full version: pdf
M. Khan, G. Pandurangan, N. D. Pham, A. Vullikanti, and Q. Zhang. A Multi-criteria Approximation Algorithm for Influence Maximization with Probabilistic Guarantees, Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), 2020. pdf
S. Chatterjee, G. Pandurangan, and N.D. Pham. Distributed MST: A Smoothed Analysis, Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN), 2020. https://arxiv.org/abs/1911.02628
R. Fathi, Anisur Rahaman Molla, and G. Pandurangan. Efficient Distributed Community Detection in the Stochastic Block Model, 39th IEEE International Conference on Distributed Computing Systems (ICDCS), 2019. pdf
Mohamad Ahmadi, Fabian Kuhn, Anisur Rahaman Molla, Shay Kutten, Gopal Pandurangan. The Communication Cost of Information Spreading in Dynamic Networks, 39th IEEE International Conference on Distributed Computing Systems (ICDCS), 2019. pdf
S. Chatterjee, G. Pandurangan, and P. Robinson. Network-size Estimation in Small-world Networks under Byzantine Faults, 33rd International Parallel and Distributed Processing Symposium (IPDPS), 2019. pdf
R. Gmyr and G. Pandurangan. Time-Message Tradeoffs in Distributed Algorithms, 32nd International Symposium on Distributed Computing (DISC), 2018. pdf
J. Augustine, and A. R. Molla, and G. Pandurangan. Sublinear Message Bounds for Randomized Agreement, 37th ACM Symposium on Principles of Distributed Computing (PODC), 2018. pdf
G. Pandurangan, P. Robinson, and M. Scquizzato. On the Distributed Complexity of Large-Scale Graph Computations, 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018. pdf.
A. R. Molla and G. Pandurangan. Local Mixing Time: Distributed Computation and Applications, 32nd International Parallel and Distributed Processing Symposium (IPDPS), 2018. pdf.
S. Chatterjee, R. Fathi, G. Pandurangan, and N. Dinh Pham. Fast and Efficient Distributed Construction of Hamiltonian Cycles in Random Graphs, 38th International Conference on Distributed Computing Systems (ICDCS), 2018. pdf
S. Chatterjee, G. Pandurangan, and P. Robinson. Complexity of Leader Election: A Chasm at Diameter Two, 19th International Conference on Distributed Computing and Networking (ICDCN), 2018. Top Nomination for the Best Paper Award. pdf
G. Pandurangan, P. Robinson, and M. Scquizzato. A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees, 49th ACM Symposium on Theory of Computing (STOC), 2017. pdf
A. R. Molla and G. Pandurangan. Distributed Computation of Mixing Time, 18th International Conference on Distributed Computing and Networking (ICDCN), 2017 (short paper). pdf
John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan and Rajmohan Rajaraman. Information Spreading in Dynamic Networks under Oblivious Adversaries, 30th International Symposium on Distributed Computing (DISC), 2016. https://arxiv.org/abs/1607.05645
G. Pandurangan, D. Peleg, and M. Scquizzato. Message Lower Bounds via Efficient Network Synchronization, 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2016. pdf
G. Pandurangan, P. Robinson, and M. Scquizzato. Fast Distributed Algorithms for Connectivity and MST in Large Graphs, 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016. pdf
M. Rahman, H. Nguyen, J. Subhlok, and G. Pandurangan. Checkpointing to minimize completion time for Inter-dependent Parallel Processes on Volunteer Grids, 16th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing,(CCGrid), 2016 (short paper). pdf
J. Augustine, G. Pandurangan, P. Robinson, S. Roche, and E.Upfal. Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks, Proceedings of IEEE Symposium on the Foundations of Computer Science (FOCS), 2015. pdf
J. Augustine, G. Pandurangan, and P. Robinson. Fast Byzantine Leader Election in Dynamic Networks, Proceedings of 29th International Symposium on Distributed Computing (DISC), 2015. pdf
J. Hegeman, G. Pandurangan, S. Pemmaraju, V. Sardeshmukh, and M. Scquizzato. Towards Optimal Bounds in the Congested Clique: Graph Connectivity and MST, ACM Symposium on Principles of Distributed Computing (PODC), 2015. pdf
H. Klauck, D. Nanongkai, G. Pandurangan, and P. Robinson. Distributed Computation of Large-scale Graph Problems, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015. https://arxiv.org/abs/1311.6209
S. Kutten, D. Nanongkai, G. Pandurangan, and P. Robinson. Distributed Symmetry Breaking in Hypergraphs, 28th International Symposium on Distributed Computing (DISC), 2014. https://arxiv.org/abs/1405.1649
M. Elkin, H. Klauck, D. Nanongkai, and G. Pandurangan. Can Quantum Communication Speedup Distributed Computation?, ACM Symposium on Principles of Distributed Computing (PODC), 2014. pdf
A. Das Sarma, A. Molla, and G. Pandurangan. Distributed Computation of Sparse Cuts via Random Walks, Proceedings of the 16th International Conference on Distributed Computing and Networking (ICDCN), 2015. pdf
G. Pandurangan, P. Robinson, and A. Trehan. DEX: Self-healing Expanders, 28th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2014. pdf
J. Augustine, G. Pandurangan, and P. Robinson. Fast Byzantine Agreement in Dynamic Networks, 32th ACM Symposium on Principles of Distributed Computing (PODC), 2013. pdf
S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan. On the Complexity of Universal Leader Election, 32th ACM Symposium on Principles of Distributed Computing (PODC), 2013. Invited to Journal of the ACM (One of the two papers to be invited to JACM from PODC 2013.) pdf
J. Augustine, A. Molla, E. Morsy, G. Pandurangan, P. Robinson, and E. Upfal. Storage and Search in Dynamic Peer-to-Peer Networks, 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013. pdf
C. Dutta, G. Pandurangan, R. Rajaraman, and S. Roche. Coalescing-Branching Random Walks on Graphs, 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013. pdf
D. Harris, E. Morsy, G. Pandurangan, P. Robinson and A. Srinivasan. Efficient Computation of Balanced Structures, Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), 2013. pdf
C. Dutta, G. Pandurangan, R. Rajaraman, Z. Sun, and E. Viola. On the Complexity of Information Spreading in Dynamic Networks, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. pdf
A. Das Sarma, A. R. Molla, G. Pandurangan and E. Upfal. Fast Distributed PageRank Computation, Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN), 2013. pdf
S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan. Sublinear Bounds for Randomized Leader Election, Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN), 2013. Best Paper Award. pdf
A. Das Sarma, A.R. Molla and G. Pandurangan. Fast Distributed Computation in Dynamic Networks via Random Walks, 26th International Symposium on Distributed Computing (DISC), 2012. http://arxiv.org/abs/1205.5525. Journal version.
M. Khan, V.S. Anil Kumar, G. Pandurangan, and G. Pei. A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model, 26th International Symposium on Distributed Computing (DISC), 2012. (Brief Annoucement). Full version: http://arxiv.org/abs/1206.1113
B. Haeupler, G. Pandurangan, David Peleg, Rajmohan Rajaraman, and Zhifeng Sun. Discovery Through Gossip, 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012. http://arxiv.org/abs/1202.2092
A. Das Sarma, M. Dinitz, and G. Pandurangan. Efficient Computation of Distance Sketches in Distributed Networks, 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012. http://arxiv.org/abs/1112.1210. Journal version.
L. He, F. Vandin, G. Pandurangan, and C. Bailey-Kellogg. BALLAST: Ball-based Algorithms for Structural Motifs, Proceedings of 16th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2012. pdf
A. Das Sarma, A.R. Molla, and G. Pandurangan. Near-Optimal Random Walk Sampling in Distributed Networks, Proceedings of the IEEE INFOCOM, 2012. pdf
J. Augustine, G. Pandurangan, P. Robinson, and E.Upfal. Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012. http://arxiv.org/abs/1108.0809 Journal version.
G. Pandurangan and A. Trehan. X-heal: Localized Self-Healing Using Expanders, 30th ACM Symposium on Principles of Distributed Computing (PODC), 2011. Full version: http://arxiv.org/abs/1104.0882 pdf
D. Nanongkai, A. Das Sarma, and G. Pandurangan. A Tight Unconditional Lower Bound on Distributed Random Walk Computation, 30th ACM Symposium on Principles of Distributed Computing (PODC), 2011. pdf
A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed Verification and Hardness of Distributed Approximation, 43rd ACM Symposium on Theory of Computing (STOC), 2011. Invited to SICOMP special issue for STOC 2011. pdf Arxiv version: http://arxiv.org/abs/1011.3049
A. Das Sarma, D. Nanongkai, G. Pandurangan, and P. Tetali. Efficient Distributed Random Walks with Applications, 29th ACM Symposium on Principles of Distributed Computing (PODC), July 2010. Arxiv version: http://arxiv.org/pdf/0911.3195 Journal version
J. Chen and G. Pandurangan. Optimal Gossip-Based Aggregate Computation, 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2010. http://arxiv.org/pdf/1001.3242
A. Das Sarma, D. Nanongkai, and G. Pandurangan. Fast Distributed Random Walks, in Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC) 2009. pdf. Journal version
J. Chen, G. Pandurangan, and J. Hu. Locality-based Aggregate Computation in Wireless Sensor Networks, in Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC) 2009. (Brief Announcement). pdf.
M. Khan, V.S. Anil Kumar, M. Marathe, G. Pandurangan, and S.S. Ravi. Bi-criteria Approximation Algorithms for Power-Efficient and Low-Interference Topology Control in Unreliable Ad hoc Networks, in IEEE INFOCOM 2009. pdf.
M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, in Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC) 2008. pdf.
Y. Choi, M. Khan, V.S.A. Kumar, and G. Pandurangan. Energy-Optimal Distributed Algorithms for Minimum Spanning Trees, 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008. pdf.
F. Xiong, G. Pandurangan, and C. Bailey-Kellogg. Contact Replacement for NMR Resonance Assignment, The 16th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB), 2008. pdf.
A. Ferrante, G. Pandurangan, and K. Park. On the Hardness of Optimization in Power Law Graphs, 13th Annual International Computing and Combinatorics Conference (COCOON), 2007. pdf
M. Khan and G. Pandurangan. A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, 20th International Symposium on Distributed Computing (DISC), 2006. Best Student Paper Award. LNCS 4167, Springer-Verlag, 2006. pdf
A. Ferrante, G. Pandurangan, and K. Park. Complexity of Combinatorial Optimization in Power-Law Graphs, SIAM Conference on Discrete Mathematics, 2006. pdf
P. Drineas, A. Javed, M. Ismail, G. Pandurangan, R. Virrankoski, and A. Savvides. Distance Matrix Reconstruction from Incomplete Information for Sensor Network Localization, Third Annual IEEE Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (SECON) , 2006. pdf
S. Jagannathan, G. Pandurangan, and S. Srinivasan. Query Protocols for Highly Resilient Peer-to-Peer Networks, 19th International Conference on Parallel and Distributed Computing Systems (PDCS), 2006. pdf
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
M. Fouad, S. Fahmy, and G. Pandurangan. Latency-Sensitive Power Control for Wireless Ad Hoc Networks, in Proceedings of the 1st ACM International Workshop on QoS and Security for Wireless and Mobile Networks, 2005. pdf
G. Pandurangan and G. Park. Analysis of a Randomized Protocols for Conflict-Free Distributed Access, in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2005. pdf
G. Pandurangan and W. Szpankowski. A Universal Online Caching Algorithm based on Pattern Matching, in Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2005. pdf
J. Chen, G. Pandurangan, and D. Xu. Robust Aggregates Computation in Wireless Sensor Networks: Distributed Randomized Algorithms and Analysis, Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), 2005. Full version
G. Pandurangan. Entropy-based Bounds for Online Algorithms, Invited paper at the 38th Annual Conference on Information Sciences and Systems (CISS), Princeton University, NJ, 2004. pdf
C. Bailey-Kellog, S. Chainraj, and G. Pandurangan. A Random Graph Approach to NMR Sequential Assignment, in 8th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004. pdf
G. Pandurangan, P. Raghavan, and E. Upfal. Using PageRank to Characterize Web Structure, Preliminary version in Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Singapore, LNCS 2387, Springer-Verlag , 330-339, 2002. pdf
G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks, in Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2001. pdf
G. Pandurangan and E. Upfal. Can Entropy Characterize Performance of Online Algorithms?, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001. pdf
M. Hauskrecht, G.Pandurangan, and E.Upfal. Computing Near-Optimal Strategies for Stochastic Investment Planning Problems, in Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI) 1999. pdf
G. Pandurangan and E. Upfal. Static and Dynamic Evaluation of QoS Properties, in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), 1999. pdf
G. Pandurangan and C.P. Rangan. Edge-Disjoint Paths in Permutation Graphs, in Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC), Beijing, LNCS 834, Springer-Verlag, pp. 208-216, 1994.
Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan. Distributed MIS in O(log log n) Awake Complexity, Invited to the Distributed Computing Journal special issue of the best papers of PODC 2023. https://arxiv.org/pdf/2204.08359.pdf
J. Augustine, K. Hourani, A. Molla, G. Pandurangan, A. Pasic. Scheduling Mechanisms to Control the Spread of Covid-19, PLoS ONE 17(9): e0272739, 2022. https://doi.org/10.1371/journal.pone.0272739
G. Pandurangan, P. Robinson, and M. Scquizzato. On the Distributed Complexity of Large-scale Graph Computations, Invited and accepted to ACM Transactions on Parallel Computing, 8(2): 7:1-7:28, 2021. Special issue of the best papers of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018. pdf
G. Pandurangan, P. Robinson, and M. Scquizzato. A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees, ACM Transactions on Algorithms, 2020, 16(1): 13:1-13:27. pdf
S. Chatterjee, G. Pandurangan, and P. Robinson. Complexity of Leader Election in Diameter-Two Networks, Distributed Computing, 2020, 33(2): 189-205. pdf
G. Pandurangan, D. Peleg, and M. Scquizzato. Message Lower Bounds via Efficient Network Synchronization, Theoretical Computer Science, 2020, 810, 82-95. Invited to the special issue of the best papers of 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2016. pdf
G. Pandurangan, P. Robinson, and M. Scquizzato. Fast Distributed Algorithms for Connectivity and MST in Large Graphs, Invited and accepted to ACM Transactions on Parallel Computing, 2018, 5(1): 4:1-4:22. Special issue of the best papers of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016. pdf
C. Dutta, G. Pandurangan, R. Rajaraman, and S. Roche. Coalescing-Branching Random Walks on Graphs, Invited and accepted to ACM Transactions on Parallel Computing, 2(3), 20: 2015. Special issue of the best papers of ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013. pdf
S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan. On the Complexity of Universal Leader Election, Journal of the ACM, 62(1), 7, 2015. One of the two papers invited from the 32th ACM Symposium on Principles of Distributed Computing (PODC), 2013. pdf
A. Das Sarma, A. R. Molla, G. Pandurangan and E. Upfal. Fast Distributed PageRank Computation, Invited to Theoretical Computer Science, 561: 113-121 (2015). Special issue of best papers of the 14th International Conference on Distributed Computing and Networking (ICDCN), 2013. pdf
G. Pandurangan, P. Robinson, and A. Trehan. DEX: Self-healing Expanders, Distributed Computing, 29(3): 163-185 (2016). pdf
S. Kutten, G. Pandurangan, D. Peleg, P. Robinson and A. Trehan. Sublinear Bounds for Randomized Leader Election, Invited to Theoretical Computer Science, 561: 134-143 (2015). Special issue of best papers of the 14th International Conference on Distributed Computing and Networking (ICDCN), 2013. Best Paper Award. pdf
J. Augustine, G. Pandurangan, P. Robinson, and E.Upfal. Distributed Agreement in Dynamic Peer-to-Peer Networks, Journal of Computer and System Sciences, 81(7), 1088-1107, 2015. pdf
D. Harris, E. Morsy, G. Pandurangan, P. Robinson and A. Srinivasan. Efficient Computation of Sparse Structures, Random Structures and Algorithms, 49(2), 332-344, 2016. pdf
G. Pandurangan and A. Trehan. Xheal: A Localized Self-healing Algorithm using Expanders, Distributed Computing, 27(1), 39-54, 2014. pdf
A. Das Sarma, A.R. Molla, and G. Pandurangan. Distributed Computation in Dynamic Networks via Random Walks, Theoretical Computer Science, 581, 45-66, 2015. pdf
A. Das Sarma, A.R. Molla and G. Pandurangan. Efficient Random Walk Sampling in Distributed Networks, Journal of Parallel and Distributed Computing, 77, 84-94, 2015. pdf
A. Das Sarma, M. Dinitiz, and G. Pandurangan. Efficient Distributed Computation of Distance Sketches in Networks, Distributed Computing, 28(5), 309-320, 2015. pdf
B. Haeupler, G. Pandurangan, David Peleg, Rajmohan Rajaraman, and Zhifeng Sun. Discovery Through Gossip, Random Structures and Algorithms, 48(3), 565-587, 2016. pdf
A. Das Sarma, D. Nanongkai, G. Pandurangan, and P. Tetali. Distributed Random Walks, Journal of the ACM (JACM), Volume 60 Issue 1, (Article 2) February 2013, 31 pages. pdf
L. He, F. Vandin, G. Pandurangan, and C. Bailey-Kellogg. BALLAST: Ball-based Algorithms for Structural Motifs, Journal of Computational Biology (special issue of RECOMB 2012), 20(2): 137-151, 2013. pdf
A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed Verification and Hardness of Distributed Approximation, SIAM Journal on Computing, 41(5), 2012, 1235–1265. Invited paper to the special issue of the best papers of ACM STOC 2011. pdf
J. Chen and G. Pandurangan. Almost-Optimal Gossip-Based Aggregate Computation, SIAM Journal on Computing, 41(3), 455-483, 2012. pdf
T. Jacobs and G. Pandurangan. Stochastic Analysis of a Churn-Tolerant Structured Peer-to-Peer Scheme, Peer-to-Peer Networking and Applications, 6(1), 2013, 1-14. pdf.
M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, Distributed Computing, 25(3): 189-205, 2012. Published online first at journal website. pdf.
S. Muthukrishnan and G. Pandurangan. Thresholding Random Geometric Graph Properties Motivated by Ad Hoc Sensor Networks, Journal of Computer and System Sciences, 76(7), 2010, 686-696. pdf. journal link
G. Pandurangan and W. Szpankowski. A Universal Online Caching Algorithm based on Pattern Matching, Algorithmica, 57(1), 2010, 62-73. Preliminary version in Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2005. 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, 1297-1304. pdf.
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
A. Ferrante, G. Pandurangan, and K. Park. On the Hardness of Optimization in Power-Law Graphs, Theoretical Computer Science, vol. 393, 2008, 220-230. Preliminary version in the 13th Annual International Computing and Combinatorics Conference (COCOON), 2007. pdf.
F. Xiong, G. Pandurangan, and C. Bailey-Kellogg. Contact Replacement for NMR Resonance Assignment, Bioinformatics , 24(13), 2008, i205-i213. pdf.
T. Czajka and G. Pandurangan. Improved Random Graph Isomorphism, Journal of Discrete Algorithms, vol. 6, 85-92, 2008. pdf
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. Preliminary version in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2005. pdf
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. Journal link. Preliminary version in 20th International Symposium on Distributed Computing (DISC), 2006. Best Student Paper Award. LNCS 4167, Springer-Verlag, 2006. pdf.
M. Khan, G. Pandurangan, and V.S.A. Kumar. A Simple Randomized Scheme for Constructing Low-Weight K-Connected Spanning Subgraphs with Applications to Distributed Algorithms, Theoretical Computer Science, vol. 385(1-3), 101-114, 2007. journal link pdf
G. Pandurangan and E. Upfal. Entropy-based Bounds for Online Algorithms, ACM Transactions on Algorithms, 3(1), Feb., 2007. Preliminary versions in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001 and 38th Annual Conference on Information Sciences and Systems(CISS), Princeton University, NJ, 2004. pdf
H. Kamichetty, C. Bailey-Kellogg, and G. Pandurangan. An Efficient Randomized Algorithm for Contact-Based NMR Backbone Resonance Assignment, Bioinformatics, 22(2), 2006, 172-180. abstract , 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. Preliminary version in Proceedings of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), 2005. pdf
G. Pandurangan, P. Raghavan, and E. Upfal. Using PageRank to Characterize Web Structure, Internet Mathematics, 3(1), 2006, 1-20. Preliminary version in Proceedings of the 8th Annual International Conference on Combinatorics and Computing (COCOON), Singapore, LNCS 2387, Springer-Verlag , 330-339, 2002. pdf
G. Pandurangan. On a Simple Randomized Algorithm for Finding a 2-Factor in Sparse Graphs, Information Processing Letters, Volume 95, Issue 1 , 2005, 321-327. pdf
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. Invited paper. Preliminary version in 8th Annual International Conference on Research in Computational Biology (RECOMB), 2004. pdf.
P. Chaitanya Das, G. Srinivasa Murthy, G. Pandurangan, and P.C. Deshmukh. The Real Effects of Pseudo-forces, Resonance 9(6), 2004, 74-85.
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. Preliminary version in Proceedings of the 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 2001. pdf
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. pdf
G. Pandurangan and E. Upfal. Static and Dynamic Evaluation of QoS Properties, Journal of Interconnection Networks, Vol. 1, No. 2 (2000), pp. 135-150. Preliminary version in Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), 1999. pdf
G. Pandurangan and C.P. Rangan. Edge-Disjoint Paths in Permutation Graphs, Discussiones Mathematicae- Graph Theory 15 (1995) pp. 59-72. Preliminary version in Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC), Beijing, LNCS 834, Springer-Verlag, pp. 208-216, 1994.
G. Pandurangan and C.P. Rangan. A Linear Time Algorithm for the Two Paths Problem on Permutation Graphs, Discussiones Mathematicae- Graph Theory 15 (1995) pp. 147-166.
G. Pandurangan, C. R. Satyan, and C. P. Rangan. Efficient Algorithms for Minimal Disjoint Path Problems on Chordal Graphs, Discussiones Mathematicae - Graph Theory 15 (1995) pp. 119-145.