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.

**1.
**__Network Effects of Risk Behavior Change
following Prophylactic Intervention __

** **with R. Rajaraman, Z. Sun and A. Vullikanti.

To appear in *PLOS ONE* 2013.

**2.
**__Cache me if you can: Capacitated
Selfish Replication Games__

** **with R. Gopalakrishnan, N. Karuturi, D. Kanoulas, C. Pandurangan and R.
Rajaraman.

Proceedings
of *LATIN* 2012.

**3.
**__Existence Theorems and Approximation
Algorithms for Generalized Network Security Games__

** **with V. S. Anil Kumar, R. Rajaraman and Z. Sun.

Proceedings of *IEEE ICDCS*
2010.

**4.
**__Reducibility among Fractional Stability
Problems__

** **with S. Kintali, L. Poplawski, R. Rajaraman and S. Teng.

Proceedings of *IEEE FOCS*, pp.
283-292, 2009.

**5.
**__Bounded Budget Connection (BBC) Games or
how to make Friends and Influence People on a Budget__

** **with N. Laoutaris, L. Poplawski, R. Rajaraman and S. Teng.

Proceedings of *ACM PODC*, pp.
165-174, 2008.

Presents
a game-theoretic formulation of the problem of forming connections in a social
network.

**6.
**__The Confluent Capacity of the Internet:
Congestion vs. Dilation__

** **with J. Chen, M. V. Marathe and R. Rajaraman.

Proceedings of *IEEE ICDCS*, 5,
2006. (Best Paper Award)

Simple
randomized scheme for achieving confluent flow with near optimal congestion and
dilation in preferential attachment graphs.

**7.
****(Almost) Tight bounds and Existence Theorems
for Confluent Flows**

with J. Chen, R. Kleinberg, L. Lovasz, R. Rajaraman and A. Vetta.

Proceedings of *Symposium on Theory of Computing (STOC)*,
pp. 529-538, 2004. The paper is accepted to the *Journal of the ACM*.

Tight upper and lower (log
n) bounds on the congestion of a confluent flow are proved.

**8.
****Meet and Merge: Approximation Algorithms for
Confluent Flows**

with J. Chen and R. Rajaraman.

Proceedings of *Symposium on Theory of Computing (STOC)*,
pp. 373-382, 2003. The paper was invited to, and appeared in, a special issue
of the *Journal of Computer Systems and
Sciences *72(3), pp. 468-489, 2006.

The notion of a confluent flow, introduced in this paper, characterizes Internet flows. A constant factor hardness result and a Ön approximation algorithm are presented for the minimum congestion of a confluent flow.

**9.
****Group-independent Spanning Tree for Data
Aggregation in Dense Sensor Networks**

with L. Jia, G. Noubir and
R. Rajaraman.

Proceedings of *IEEE* *DCOSS*,
pp. 282-304, 2006.

Universal algorithm and associated protocol for data aggregation in
sensor networks embedded on the plane.

**10.
****Universal approximations for TSP, Steiner tree
and set cover**

with L. Jia, G. Lin, G.
Noubir and R. Rajaraman.

*Symposium on Theory of Computing (STOC)*, pp. 386-395, 2005.

A
Sigma-2 model for approximation algorithms. Polylog approximation algorithms
for metric TSP and Steiner tree.

**11.
****Maygh: Building a CDN from client web browsers **

with L. Zhang, F. Zhou and
A. Mislove.

Proceedings of *ACM/EuroSys*, 2013.

**12.
****Prediction of arrival of Nodes in a Scale-free
Network **

with V. Mahantesh, S.
Iyengar, M. Vijesh, S. Nayak and N. Shenoy.

Proceedings of *ACM/IEEE ASONAM*, 2012.

**13.
****WebCloud: Recruiting Web Users for Content
Distribution **

with F. Zhou, E. Franco,
L. Zhang, R. Revis and A. Mislove.

Proceedings of *NCA*, 2012.

**14.
****Home is where the (Fast) Internet is: Flat-rate
Compatible Incentives for Reducing Peak Load **

with P. Chhabra, N.
Laoutaris and P. Rodriguez.

Accepted to *ACM SIGCOMM Workshop on Home Networking,
HOMENETS’10*, 2010.

**15.
****Algorithms for Constrained Bulk-Transfer
of Delay-Tolerant Data **

with P. Chhabra, V.
Erramilli, N. Laoutaris and P. Rodriguez.

Accepted to *IEEE ICC*, 2010.

**16.
****Delay Tolerant Bulk Data Transfers on the
Internet **

with N. Laoutaris, G.
Smaragdakis and P. Rodriguez.

Proceedings of *ACM SIGMETRICS*, pp. 229-238, 2009.

Using store-and-forward to
improve the transfer of bulk data over the Internet.

**17.
****Scaling Laws for the Internet over Urban
Regions **

with V. S. Anil Kumar, M.
Marathe, M. Thakur and S. Thulasidasan.

Accepted to CAIDA’s *ISMA WIT*, (Short Paper) 2006.

A study of the topology of
the Internet over metropolitan areas.

**18. ****Towards a Topology Generator Modeling
AS Relationships **

with X. Dimitropoulos, G.
Riley and D. Krioukov.

Proceedings of *IEEE International Conference on Network
Protocols (ICNP)*, (Short Paper) 2006.

A generator for AS-level
graphs that captures inter-AS relationships.

**19.
****A methodology for estimating
inter-domain web traffic demand**

with A. Feldmann, O. Maennel, N. Kammenhuber, B. Maggs and R. de Prisco.

Proceedings of *Internet Measurement Conference (IMC)*,
pp. 322-335, 2004.

Estimation of inter-domain
traffic combining CDN data with trace data.

**20.
****Minimum energy accumulative routing in wireless
networks**

with J. Chen, L. Jia, X.
Liu and G. Noubir.

Proceedings of *INFOCOM*, vol. 3, pp. 1875-1886, 2005.

Bounds (upper and lower) on
accumulative energy routing.

**21.
****Managing a portfolio of overlay paths**

with D. Antonova, A. Krishnamurthy and Z. Ma.

Proceedings of *Networking and Operating Systems Support for
Digital Audio and Video* (*NOSSDAV)*,
pp. 30-35, 2004.

A mean-variance framework
for optimizing overlay paths.

**22.
****Improving minimum cost spanning trees by
upgrading nodes**

with S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi
and H-C. Wirth.

*Journal of Algorithms*, 33(1), pp. 92-111, 1999.

**23.
****Improving spanning trees by upgrading
nodes**

with S.O. Krumke, H. Noltemeier, H-C. Wirth, M.V. Marathe, R.
Ravi, and S.S. Ravi.

*Theoretical Computer Science*, 221(1-2), pp. 139-155,
1999. A preliminary version appeared in *International Colloquium on Automata,
Languages and Programming (ICALP)*, LNCS 1256, pp. 281-291, 1997.

**24.
****Bicriteria network design problems**

with M.V. Marathe, R. Ravi, S.S. Ravi, D. Rosenkrantz and H. Hunt.

*Journal of Algorithms*, 28(1), pp. 142-171, 1998. A preliminary version
appeared in *International Colloquium on
Automata, Languages and Programming (ICALP)*, LNCS 944, pp. 487-498, 1995.

**25.
****Improved results on service-constrained
network design problems**

with M.V. Marathe and R. Ravi.

*Network Design: Connectivity and Facilities Location*, P.M. Pardalos and D.Z. Du,
editors, DIMACS Series, Vol. 40, AMS, pp. 269-276, 1998.

with R. Panigrahy,
Ravi Kumar and A. Russell.

*Information Processing Letters*, 62, pp. 295-300, 1997.

**27.
****Service-constrained network design problems**

with M. V. Marathe and
R. Ravi.

*Nordic Journal of Computing*, 3(4), pp. 367-387, 1996. A preliminary version
appeared in *Scandinavian Workshop on
Algorithm Theory (SWAT)*, LNCS 1097, pp. 28-40, 1996.

**28.
****Spanning trees short or small**

with R. Ravi, M.V.
Marathe, D. Rosenkrantz and S.S. Ravi.

*SIAM Journal of Discrete Mathematics*, 9(2), pp. 178-200, 1996. A preliminary version (with a coda!) appeared in *ACM-SIAM Symposium on Discrete Algorithms
(SODA)*, pp. 546-555, 1994

**29.
****On completing Latin Squares**

with Iman Hajirasouliha, Hossein Jowhari
and Ravi Kumar.

*Symposium on Theoretical Aspects of Computer Science (STACS)*, 2007.

**30.
****Approximating Latin square extensions **

with Ravi Kumar and A. Russell.

*Algorithmica*, 24(2), pp. 128-138, 1999. A preliminary version appeared in *International Conference on Computation and
Combinatorics (COCOON)*, LNCS 1090, pp. 280-289, 1996.

**31.
****Faster algorithms for optical switch
configurations**

with Ravi Kumar and A. Russell.

*IEEE International Conference on Communications (ICC)*, pp. 1320-1324, 1997.

**32.
****Scheduler Vulnerabilities and Coordinated
Attacks in Cloud Computing **

with F. Zhou, M. Goel and P. Desnoyers.

To appear in *Journal of Computer Security.*
Preliminary version appeared in NCA 2011.

**33.
****SamaritanCloud: Secure and Scalable
Infrastructure for enabling Location-based Services **

with A. Samanta and F. Zhou.

Proceedings of *IFIP Networking*, 2013. One of 6 papers
selected from 50 for special issue of Computer Communications Journal.

**34.
****Evaluating Encrypted Boolean Functions
on Encrypted bits: Secure decision-making on the Black side **

with R. Krishnan.

Proceedings of *SPIE DSS*, 2013.

**35.
****Optimization of Directional Antenna
Network Topology in Airborne Networks **

with G. Hadynski, S. B. Lee, G. Rajappan, X. Wang and F. Zhou.

Proceedings of *IEEE MILCOM*, 2010.

**36.
****Policy-Agile Encrypted Networks Via Secure
Function Computation **

with R. Krishnan.

Proceedings of *IEEE MILCOM*, 2010.

**37.
****HARD-DNS: Highly-Available
Redundantly-Distributed DNS **

with C. Gutierrez, R. Krishnan and F. Zhou.

Proceedings of *IEEE MILCOM*, 2010.

with K. Bertolino.

Proceedings of *IEEE International Conference on
Technologies for Homeland Security*, 2008.

**39.
****A Game-Theoretic Framework for Bandwidth
Attacks and Statistical Defenses**

with M. Snyder and M. Thakur.

Proceedings
of *IEEE LCN (Local Computer Networks)
Conference*, 2007.

**40.
****SPREAD: Foiling Jammers using Multi-Layer Agility
**

with X. Liu, G. Noubir and S. Tan.

Proceedings of *INFOCOM Minisymposium, *2007.

Idea for foiling jammers by
mechanism hopping across layers using cryptographic coordination.

**41.
****Steganographic Communication in
Ordered Channels **

with Ch. Ravi Chandra, A. Kumarasubramaniam, G. Noubir, C. Pandu Rangan and R.
Manokaran.

Proceedings of *Information Hiding, IH2006, *LNCS*,* 2006.

Estimation of the amount of
information that can be embedded in the sequencing of packets in an ordered
channel, such as TCP. Optimal codes with encoding/decoding algorithms are
provided and an open problem due to Lehmer is resolved.

with R. Gennaro, D. Leigh and W. Yerazunis.

Proceedings of *AsiaCrypt, *LNCS pp. 276-292*,* 2004.

A generalization of
Schnorr’s zero knowledge scheme to multiple identities is presented. Details of
a smart card implementation using bi-directional LEDs are given. The scheme
allows for an efficient transfer of privileges from one smart card to another.

**43.
****Alternation in interaction**

with M. Kiwi, C. Lund,
A. Russell and D. Spielman.

*Computational Complexity*, 9(3-4), pp. 202-246, 2000. A preliminary version
appeared in *IEEE Conference on Structure
in Complexity Theory*, pp. 294-303, 1994.

**44.
****A note on the asymptotics and
computational complexity of graph distinguishability**

with A. Russell.

*Electronic
Journal of Combinatorics, 5(1), R23*, 1998.

**45.
****Symmetric alternation captures BPP**

with A. Russell.

*Computational Complexity*, 7(2), pp. 152-162, 1998. A preliminary version
appeared in *Workshop on Interactive Proof
Systems,* Weizmann Institute, Israel, 1995.

We introduce S_{2} –
a complexity class that captures symmetric alternation and prove a number of
interesting facts about this class. Ran Canetti independently discovered S_{2}.
Later Cai proved a very interesting result about this class and Sengupta
observed that in the tightest form of the famous Karp-Lipton theorem, the
polynomial-time hierarchy collapses to S_{2}. Read all about it in
Lance Fortnow’s complexity theory blog where it attained the status of “complexity
class of the week” for the week of August 28, 2002.

**46.
****The relationship between probabilistically
checkable debate systems, IP and PSPACE**

with A. Russell.

*Information Processing Letters*, 53(2), pp. 61-68, 1995.

**47.
****PhoneGuard: A smartphone in the coalmine**

with N. Mayor, F. Wagen and A. Samanta.

Proceedings of *ACM ACWR
(International Conference on Wireless Technologies for Humanitarian Relief)*,
2011.

**48.
**

**49.
****Preprocessing DNS Log Data for
Effective Data Mining**

with M. Snyder and M. Thakur.

Proceedings
of *IEEE ICC (International Conference on
Communications)*, 2009.

**50. ****MOVARTO: Virtual Server Migration across
Networks using DNS and Route Triangulation**

**
**with N.
Faber.

*VMWorld*
2007.

Extends the concept of OS virtualization
to network virtualization.

**51.
****Unweaving a web of documents**

with R. Guha, Ravi Kumar
and D. Sivakumar.

Proceedings of *Knowledge Discovery and Data Mining (KDD),*
pp. 574-579, (Short Paper) 2005.

Algorithms for decomposing a
collection of time-stamped documents into threads.

**52.
****Expressiveness and complexity of
crosscut languages**

with K. Lieberherr and J.
Palm.

Accepted to *FOAL*, 2005.

Algorithms and hardness
results for a class of crosscut languages.

**53.
****A note on embedding complete graphs into
hypercubes**

with M. Klugerman and
A. Russell.

*Discrete Mathematics*, 186, pp. 1-3, 1998.

It is shown that complete
graphs of size n can be embedded into hypercubes so as to minimize the sum of
edge dilations in a uniform way for all n except n =4 and n = 8. This explains
the anomalous factor of approximation obtained for a natural algorithm for the
multicut problem. This was the first paper to give me an Erdos number of 2;
Mike Klugerman has coauthored a paper with Erdos.

**54.
****Treewidth of circular-arc graphs**

with K.S. Singh and
C.P. Rangan.

*SIAM Journal of Discrete Mathematics*, 7(4), pp. 647-655, 1994. A preliminary
version appeared in *Workshop on
Algorithms and Data Structures (WADS)*, LNCS 519, p. 41, 1991.

Treewidth is a graph measure
defined by Robertson and Seymour in the course of their celebrated graph minor
project. The treewidth of a graph characterizes the complexity of many
computational problems on that graph. Here we present the first polynomial time
algorithms for computing the treewidth of the class of intersection graphs of arcs
on a circle.

**55.
****Efficient parallel shuffle recognition**

with M. Nivat, G.D.S.
Ramkumar, C.P. Rangan and A. Saoudi.

*Parallel Processing Letters*, 4(4), pp. 455-463, 1994. A preliminary version
appeared in *International Parallel
Processing Symposium (IPPS)*, pp. 112-115, 1992.

**56.
****Optimal path cover problem on block graphs
and bipartite permutation graphs**

with R. Srikant, K.S. Singh and C.P. Rangan.

*Theoretical Computer Science*, 115(2), pp. 351-357, 1993.

This paper presents the first polynomial-time algorithms for minimizing the number of paths needed to cover block graphs and bipartite permutation graphs.

MIT, 1996.

Goes from verse (see
acknowledgement) to bad.