Publications
Sample Complexity of Linear Regression Models for Opinion Formation in Networks
with H. Lin, R. Sundaram, A. Vullikanti, O. Wasim, and H. Xu
AAAI, February 2025, to appear
Online Balanced Allocation of Dynamic Components
with O. Wasim
ITCS, January 2025, to appear
Fully Dynamic (Delta+1)-Coloring Against Adaptive Adversaries
with S. Behnezhad and O. Wasim
SODA, January 2025, to appear
Competitive Capacitated Online Recoloring
with O. Wasim
ESA, September 2024
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
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
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.