Refereed Publications

  • John Augustine, Arnhav Datar, and Nischith Shadagopan, ‘‘Randomized Byzantine Gathering in Rings," OPODIS 2022.

  • Arnhav Datar, Arun Rajkumar, and John Augustine, ‘‘Byzantine Spectral Ranking," Neurips 2022.

  • John Augustine, Wahid Gulzar Bhat, Sandip Nair, ‘‘Plateau: A Secure and Scalable Overlay Network for Large Distributed Trust Applications," SSS 2022.

  • John Augustine, Khalid Hourani, Anisur Rahaman Molla, Gopal Pandurangan, Adi Pasic, ‘‘Scheduling mechanisms to control the spread of COVID-19," PLOS One, September 2022.

  • John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, Yadu Vasudev, ‘‘Byzantine Connectivity Testing in the Congested Clique," DISC 2022.

  • John Augustine, Soumyottam Chatterjee, Gopal Pandurangan, ‘‘A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash Tables," SPAA 2022.

  • John Augustine, William K. Moses Jr., Gopal Pandurangan, ‘‘Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds," PODC 2022.

  • John Augustine, Srikkanth Ramachandran, ‘‘Brief Announcement: Cooperative Guarding in Polygons with Holes," SAND 2022.

  • John Augustine, Kishore Kothapalli, and Gopal Pandurangan, “Efficient Distributed Algorithms for the k-machine model via PRAM Simulations.” IPDPS 2021.

  • Debasish Pattanayak, John Augustine, Partha Sarathi Mandal, “Randomized Gathering of Asynchronous Mobile Robots.” Theoretical Computer Science, 858: 64-80 (2021).

  • John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia, “Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols,” DISC 2020.

  • Barath Ashok, John Augustine, Aditya Mehekare, Sridhar Ragupathi, Srikkanth Ramachandran, and Suman Sourav, “Guarding a Polygon Without Losing Touch,” SIROCCO 2020.

  • John Augustine, Keerti Choudhary, Avi Cohen, David Peleg, Sumathi Sivasubramaniam, and Suman Sourav, “Distributed Graph Realizations.” IPDPS 2020.

  • John Augustine, Seth Gilbert, Fabian Kuhn, Peter Robinson and Suman Sourav, “Latency, Capacity, and Distributed Minimum Spanning Tree.” ICDCS 2020.

  • John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider, “Shortest Paths in a Hybrid Network Model.” SODA 2020.

  • Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Prashanth Srikanthan, “Minmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities.” Algorithmica, 81: 3534 (2019).

  • John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, and Christian Scheideler, "Distributed Computation in Node-Capacitated Networks.” SPAA 2019.

  • John Augustine, Anisur Rahaman Molla, and Gopal Pandurangan, “Sublinear Message Bounds for Randomized Agreement.” PODC 2018.

  • John Augustine and Sumathi Sivasubramanian, “Spartan: A Framework For Sparse Robust Addressable Networks.” Journal of Parallel and Distributed Computing, Volume 150, 2021, Pages 121-138. A preliminary version appeared in IPDPS 2018.

  • John Augustine, William K. Moses Jr., “Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs.” ICDCN 2018. arxiv

  • Ankush Agarwalla, John Augustine, William K. Moses Jr., Madhav Sankar K., Arvind Krishna Sridhar, “Deterministic Dispersion of Mobile Robots in Dynamic Rings.” ICDCN 2018. arxiv

  • John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan, Rajmohan Rajaraman, “Information Spreading in Dynamic Networks under Oblivious Adversaries.” DISC 2016.

  • John Augustine, William Kumar Moses Jr., Amanda Redlich, Eli Upfal, “Balanced Allocation: Patience is not a Virtue.” SODA 2016. PDF

  • John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, Eli Upfal, “Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks.” FOCS 2015. PDF

  • John Augustine, Ioannis Caragiannis, Angelo Fanelli, Christos Kalaitzis, “Enforcing Efficient Equilibria in Network Design Games via Subsidies.” Algorithmica 72(1): 44-82 (2015). (Preliminary version in SPAA 2012. http://arxiv.org/abs/1104.4423)

  • John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev, “Dynamics of Profit-Sharing Games.” Internet Mathematics 11(1): 1-22 (2015). (Preliminary version in IJCAI 2011. http://arxiv.org/abs/1010.5081)

  • John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal, “Distributed agreement in dynamic peer-to-peer networks.” J. Comput. Syst. Sci. 81(7): 1088-1109 (2015). (Preliminary version in SODA 2012. http://arxiv.org/abs/1108.0809)

  • Yuya Higashikawa, John Augustine, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, Yin-Feng Xu, “Minimax regret 1-sink location problem in dynamic path networks.” Theor. Comput. Sci. 588: 24-36 (2015).

  • John Augustine, Tejas Kulkarni, Sumathi Sivasubramaniam, “Leader Election in Sparse Dynamic Networks with Churn.” IPDPS 2015: 347-356.

  • John Augustine, Gopal Pandurangan, Peter Robinson, “Fast Byzantine Leader Election in Dynamic Networks.” DISC 2015: 276-291.

  • John Augustine, Sandip Das, Anil Maheshwari, Subhas C. Nandy, Sasanka Roy, Swami Sarvattomananda, “Localized geometric query problems.” Comput. Geom. 46(3): 340-357 (2013).

  • John Augustine, Qi Han, Philip Loden, Sachin Lodha, Sasanka Roy, “Tight Analysis of Shortest Path Convergecast in Wireless Sensor Networks.” Int. J. Found. Comput. Sci. 24(1): 31-50 (2013). (Preliminary version appeared in CATS 2011.)

  • John Augustine, Gopal Pandurangan, Peter Robinson, “Fast byzantine agreement in dynamic networks.” PODC 2013: 74-83

  • John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Eli Upfal, “Storage and search in dynamic peer-to-peer networks” SPAA 2013: 53-62.

  • John Augustine, Tejas Kulkarni, Paresh Nakhe, Peter Robinson, “Robust Leader Election in a Fast-Changing World.” FOMC 2013: 38-49

  • John Augustine, Sandip Das, Anil Maheswari, Subhas Nandy, Sasanka Roy, and Swami Sarvattomananda, “Localized Geometric Query Problems.” Accepted to appear in Computational Geometry - Theory and Application. http://arxiv.org/abs/1111.2918

  • Sangameshwar Patil, Sasanka Roy, John Augustine, Amanda Redlich, Sachin Lodha, and Harrick Vin, Anand Deshpande, Mangesh Gharote, and Ankit Mehrotra, “Minimizing Testing Overheads in Database Migration Lifecycle.” The 16th International Conference on Management of Data (COMAD), 2010. PDF

  • John Augustine and Nick Gravin, “On the Continuous CNN Problem,” The 21st International Symposium on Algorithms and Computation (ISAAC), 2010. http://arxiv.org/abs/1004.2393

  • John Augustine, David Eppstein, and Kevin A. Wortman, “Approximate Weighted Farthest Neighbor Queries and Minimum Dilation Stars,” The 16th Annual International Computing and Combinatorics Conference (COCOON), 2010. http://arxiv.org/abs/cs/0602029 (a bit outdated) Full version: Discrete Mathematics Algorithms and Applications, Volume 2, Issue 4, December 2010, pp. 553-565. http://dx.doi.org/10.1142/S1793830910000887

  • Deepak Jeswani, Nakul Korde, Dinesh Patil, Maitreya Natu, and John Augustine,“Probe Station Selection Algorithms for Fault Management in Computer Networks,” Second International Conference on Communication Systems and Networks (COMSNETS), 2010. PDF

  • Pranjali Pagey, John Augustine, Rahul Kelkar, and Harrick Vin, “A tool for server consolidation engagements,” In TCS Technical Architects Conference (TACTiCS), 2009.

  • John Augustine, Sudarshan Banerjee, and Sandy Irani, “Strip packing with precedence constraints and strip packing with release times,” Theoretical Computer Science, Volume 410, Issues 38-40, 6 September 2009, pp. 3792-3803. A preliminary version appeared in the Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006.

  • Mohamed Aly and John Augustine, “Online Packet Admission And Oblivious Routing In Sensor Networks,” Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), 2006.

  • John Augustine, Sandy Irani, and Chaitanya Swamy, “Optimal Power-Down Strategies,” Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004. Full version: SIAM Journal on Computing, Volume 37, Issue 5, January 2008, pp. 1499-1516.

  • John Augustine and Steven Seiden, “Linear Time Approximation Schemes for Vehicle Scheduling problems,” Proceedings of the 8th Scandinavian Workshop on Algorithm theory (SWAT), 2002. Full version: Theoretical Computer Science, Volume 324, Issues 2-3, September 2004, pp. 147-160.

Invited Publications

  • John Augustine, Gopal Pandurangan, and Peter Robinson, “Distributed Algorithmic Foundations of Dynamic Networks.” SIGACT News 47, 1 (March 2016), 69-98.

  • Ashutosh Ingole, Biswaroop Maiti, John Augustine, Krishna V. Palem, “Does customizing inexactness help over simplistic precision (bit-width) reduction? A case study.” CASES 2015: 33-34

  • Guru Prakash Arumugam, Prashanth Srikanthan, John Augustine, Krishna V. Palem, Eli Upfal, Ayush Bhargava, Parishkrati, Sreelatha Yenugula, “Novel inexact memory aware algorithm co-design for energy efficient computation: algorithmic principles.” DATE 2015: 752-757

  • Peter D. Düben, Jeremy Schlachter, Parishkrati, Sreelatha Yenugula, John Augustine, Christian C. Enz, Krishna V. Palem, T. N. Palmer, “Opportunities for energy efficient computing: a study of inexact general purpose processors for high-performance and big-data applications.” DATE 2015: 764-769

Manuscripts

  • John Augustine, Krishna V. Palem, Parishkrati. “Sustaining Moore's Law Through Inexactness.” https:arxiv.orgabs1705.01497

  • John Augustine, Khalid Hourani, Anisur Rahaman Molla, Gopal Pandurangan, Adi Pasic, “Economy Versus Disease Spread: Reopening Mechanisms for COVID 19.” https:arxiv.orgabs2009.0887