Refereed Publications

  • 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.


  • John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, Eli Upfal, “Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks.” FOCS 2015.
  • 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 [PDF] 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]
  • John Augustine, Brian Putnam, and Sasanka Roy, “Largest Empty Circle Centered on a Query Line,” Journal of Discrete Algorithms, Volume 8, Issue 2, June 2010, Pages 143-153. Preliminary draft: http://arxiv.org/abs/0809.2651Full Version: http://dx.doi.org/10.1016/j.jda.2009.10.002
  • 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. [PDF]
  • 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. [PDF]
  • 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.http://dx.doi.org/10.1016/j.tcs.2004.05.013

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