The documents listed below have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications

Stability of P2P Networks Under Greedy Peering
with L. Kiffer
SIROCCO, May 2024, Best Paper Award

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
with C. Busch, D. Q. Chen, A. Filtser, D. Hathcock and D. Hershkowitz
FOCS, November 2023

Scheduling under Non-Uniform Job and Machine Delays
with D. Stalfa and S. Yang,
ICALP, July 2023

Online Paging with Heterogeneous Cache Slots
with M. Chrobak, S. Haney, M. Liaee, D. Panigrahi, R. Sundaram, and N. Young,
STACS, March 2023

Improved Bounds for Online Balanced Graph Re-Partitioning
with O. Wasim
ESA, September 2022

Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints
with S. Pa and D. Stalfa
APOCS, January 2022

HaPPY-Mine: Designing a Mining Reward Function
with L. Kiffer
Financial Crypto, January 2021

Competitive Data-Structure Dynamization
with C. Mathieu, N. Young, and A. Yousefi
SODA, January 2021

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay
with B. Maiti, Z. Svitkina, A. Vijayaraghavan, and D. Stalfa
FOCS, November 2020

Scheduling Flows on a Switch to Optimize Response Times
with H. Jahanjou and D. Stalfa
SPAA, July 2020

Retracting Graphs to Cycles
with S. Haney, M. Liaee, B. Maggs, D. Panigrahy, and R. Sundaram
ICALP, July 2019

A Better Method to Analyze Blockchain Consistency
with L. Kiffer and A. Shelat
CCS, October 2018

Colocation, Colocation, Colocation: Optimizing Placement in the Hybrid Cloud
with S. Aiyar, K. Gupta, B. Shen, Z. Sun, and R. Sundaram
ALGOCLOUD, August 2018

Plane Gossip: Approximating Rumor Spread in Planar Graphs
with J. Iglesias, R. Ravi, and R. Sundaram
LATIN, April 2018

Improved Algorithms for Scheduling Unsplittable Flows on Paths
with H. Jahanjou and E. Kantor
ISAAC, December 2017
Algorithmica, 2023

Symmetric Interdiction for Matching Problems
with S. Haney, B. M. Maggs, B. Maiti, D. Panigrahi, and R. Sundaram
APPROX-RANDOM, August 2017

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling
with H. Jahanjou and E. Kantor
SPAA, July 2017

Information Spreading in Dynamic Networks under Oblivious Adversaries
with J. Augustine, C. Avin, M. Liaee, and G. Pandurangan
DISC, October 2016

Balls and Funnels: Energy Efficient Group-to-Group Anycasts
with J. Iglesias, R. Ravi, and R. Sundaram
COCOON, August 2016

Robust and Probabilistic Failure-Aware Placement
with M. Korupolu
SPAA, July 2016; Outstanding Paper Award

Better Bounds for Coalescing-Branching Random Walks
with M. Mitzenmacher and S. Roche
SPAA, July 2016

Robust Secret Sharing with Essentially Optimal Share Size
with A. Bishop, V. Pastro, and D. Wichs
Eurocrypt, May 2016; honorable mention for best paper award (one of top 3 papers)

Rumors over Radio, Wireless, and Telephone
with J. Iglesias, R. Ravi, and R. Sundaram
FSTTCS, December 2015

Designing Overlapping Networks for Publish-Subscribe Systems
with J. Iglesias, R. Ravi, and R. Sundaram
APPROX, August 2015

On Constructing DAG-Schedules with Large AREAs
with S. Roche and A. Rosenberg
Euro-Par, August 2014

Coupled and k-sided placements: Generalizing generalized assignment
with M. Korupolu, A. Meyerson, and B. Tagiku
IPCO, June 2014

Network effects of risk behavior change following prophylactic interventions
with V. Anil Kumar, Zhifeng Sun, and Ravi Sundaram
PLoS ONE, August 2013

Coalescing Branching Random Walks on Graphs
with Chinmoy Dutta, Gopal Pandurangan, and Scott Roche
ACM SPAA 2013; Theory of Computing Systems 2015

On the Complexity of Information Spreading in Dynamic Networks
with Chinmoy Dutta, Gopal Pandurangan, Zhifeng Sun, and Emanuele Viola
ACM-SIAM SODA 2013

Split and Join: Strong Graph Partitions and Universal Steiner Trees for Graphs
with C. Busch, C. Dutta, J. Radhakrishnan, and S. Srinivasagopalan
IEEE FOCS 2012

Discovery Through Gossip
with Bernhard Haeupler, Gopal Pandurangan, David Peleg, and Zhifeng Sun
ACM SPAA 2012

Cache me if you can: Capacitated Selfish Replication Games
with R. Gopalakrishnan, D. Kanoulas, N. Karuturi, C. Pandu Rangan, and R. Sundaram
LATIN 2012.

On the robustness of IEEE 802.11 rate adaptation algorithms against smart jamming
with Guevara Noubir, Bo Sheng, and Bishal Thapa
ACM WISEC 2011, winner of best paper award

Multicommodity Facility Location under Group Steiner Access Cost
with Laura Poplawski
SODA 2011.

Existence Theorems and Approximation Algorithms for Generalized Network Security Games
with A. Kumar, Z. Sun, and R.Sundaram
ICDCS 2010.

A General Framework for Incremental Approximation and Hierarchical Clustering
with G. Lin and C. Nagarajan and D. Williamson. 
SICOMP 2010, preliminary version in SODA 2006.

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
with G. Lin
Theory of Computing Systems 2010, special issue on selected papers from on SPAA 2007.

Reducibility among Fractional Stability Problems
with S. Kintali, L. Poplawski, R.Sundaram, and S. Teng
FOCS 2009.

Approximation Algorithms for Key Management in Secure Multicast
with A. Chan, Z. Sun, and F. Zhu
COCOON 2009.

Bounded Budget Connection Games, or How to Make Friends and Influence People, on a Budget
with N. Laoutaris, L. Poplawski, R. Sundaram, and S.-H. Teng
PODC 2008.

Approximation Algorithms for Data Placement Problems
with I. Baev, and C. Swamy
SIAM Journal on Computing, 2008.

On the Performance of IEEE 802.11 under Jamming
with E. Bayrataroglu, C. King, X. Liu, G. Noubir, and B. Thapa
In Proceedings of Infocom 2008

(Almost) Tight Bounds and Existence Theorems for Single-Commodity Confluent Flows
with J. Chen, R. Kleinberg, L. Lovasz, R. Sundaram, and A. Vetta.
In Journal of the ACM, volume 54, 2007
A preliminary version appears in STOC 2004.

A Space Lower Bound for Name-Independent Compact Routing in Trees
with K. Laing
Journal of Interconnection Networks, volume 8, September 2007.

Wave Scheduling and Routing in Sensor Networks
with A. Trigoni, Y. Yao, A. Demers, and J. Gehrke.
In ACM Transactions on Sensor Networks, volume 3, March 2007.
A preliminary version appears in DMSN 2004 a VLDB 2004 workshop.

Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networks
with R. Chakinala, A. Kumarasubramanian, K. Laing, R. Manokaran, and P. Rangan
SPAA 2006.

On the Confluent Capacity of the Internet: Congestion and Dilation
with J. Chen, M. Marathe, and R. Sundaram
ICDCS 2006; winner of best paper award

Meet and Merge: Approximation Algorithms for Confluent Flows
with J. Chen and R. Sundaram.
Journal of Computer and System Sciences, 72(3): 468-489 (2006)
A preliminary version appears in STOC 2003.

Compact Routing with Name Independence
with M. Arias, L. Cowen, K. Laing, and O. Taka
SIAM Journal on Discrete Mathematics, volume 20, pages 705--726, 2006
A preliminary version appears in SPAA 2003

Group-Independent Spanning Trees for Data Aggregation in Sensor Networks
with L. Jia, G. Noubir, and R. Sundaram
In IEEE International Conference on Distributed Computing in Sensor Systems, June 2006

Universal Approximations for Steiner Tree, TSP, and Set Cover
with L. Jia, G. Lin, G. Noubir, and R. Sundaram
STOC 2005.

Multi-Query Optimization for Sensor Networks
with N. Trigoni, Y. Yao, A. Demers, and J. Gehrke
In IEEE International Conference on Distributed Computing in Sensor Systems, June-July 2005

Hybrid Push-Pull Query Processing for Sensor Networks
with N. Trigoni, Y. Yao, A. Demers, and J. Gehrke
In GI-Conference Informatik Workshop on Sensor Networks. Berlin, Germany, September 2004.

Mobility Models for Ad Hoc Networks
with G. Lin and G. Noubir
In Proceedings of INFOCOM, March 2004

Improved Algorithms for Stretch Scheduling
with M. Bender and S. Muthukrishnan.
In Journal of Scheduling 7(3): 195-222 (2004)
A preliminary version appears in SODA 2002.

Scheduling to Minimize Average Stretch
with J. E. Gehrke, S. Muthukrishnan, and A. Shaheen
In SIAM Journal on Computing, 34(2): 433-452 (2004)
A preliminary version appears in FOCS 1999.

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems
with V. Guruswami, S. Khanna, B. Shepherd, and M. Yannakakis.
In Journal of Computer and System Sciences, 67(3), 473-496, 2003
A preliminary version appears in STOC 1999.

The Cougar Project: A Work-In-Progress Report
with A. Demers, J. Gehrke, N. Trigoni, and Y. Yao
Sigmod Record, Volume 34, Number 4, December 2003

On Local Algorithms for Topology Control and Routing in Ad hoc Networks
with L. Jia and C. Scheideler
In SPAA 2003

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes
with M. Adler, S. Khanna, and A. Rosen.
In Algorithmica, 36(2): 123--152, 2003
A preliminary version appears in SPAA 1999.

An Efficient Distributed Algorithm for Constructing Small Dominating Sets
with L. Jia and T. Suel. 
In Distributed Computing 15:193-205, 2002.
Special issue on selected papers from PODC 2001.

An Adversarial Model for Distributed Dynamic Load Balancing
with S. Muthukrishnan.
In Journal of Interconnection Networks  3:35--47, 2002.
A preliminary version appears in SPAA 1998.

Topology Control and Routing in Ad hoc Networks: A Survey
In SIGACT News 33:60-73, June 2002

A Data Tracking Scheme for General Networks
with A.W. Richa, B. Vöcking, and G. Vuppuluri.
SPAA 2001.

Approximation Algorithms for Data Placement in Arbitrary Networks
with I. Baev.
SODA 2001.

Placement Algorithms for Hierarchical Cooperative Caching
with M. R. Korupolu and C. G. Plaxton. 
In Journal of Algorithms 38:260--302, 2001.
Special issue on selected papers from SODA 1999.

Towards More Complete Models of TCP Latency and Throughput
with M. Mitzenmacher.
Journal of Supercomputing 20:137--160,  2001.  Special issue on transport protocols.

Analysis of a Local Search Heuristic for Facility Location Problems
with M. Korupolu and C. G. Plaxton. 
In Journal of Algorithms 37:146--188, 2000.
Special issue on selected papers from SODA 1998.

Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings
with J. E. Gehrke and C. G. Plaxton.
In Theoretical Computer Science 220(1):247-265, 1999.
A preliminary version appears in DISC 1997.

Tight Analyses of Two Local Load Balancing Algorithms
with B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, A. W. Richa, R. E. Tarjan, and D. Zuckerman.
In SIAM Journal on Computing, 29(1):29-64, 1999.
A preliminary version appears in STOC 1995.

A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service
with M. Rabinovich, I. Rabinovich, and A. Aggarwal.
In ICDCS 1999.

Accessing Nearby Copies of Replicated Objects in a Distributed Environment
with C. G. Plaxton and A. W. Richa.
In Theory of Computing Systems 32:241-280, 1999.
Special issue on selected papers from SPAA 1997.

On Contention Resolution Protocols and Associated Probabilistic Phenomena
with P. D. Mackenzie and C. G. Plaxton.
In Journal of the ACM 45(2):324-378, March 1998.
A preliminary version appears in STOC 1994.

Fast Fault-Tolerant Concurrent Access to Shared Objects
with C. G. Plaxton.
In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 570-579, October 1996.

Optimal Clustering for Delay Minimization
with D. F. Wong.
In IEEE Transactions on Computer-Aided Design of Intergrated Circuits and Systems , 14(1), pages 1490-1495, December 1995.
A preliminary version appears in Proceedings of the 30th Design Automation Conference, pages 309-314, June 1993.

Dissertation

Sharing Resources in Distributed Systems, December 1997.