>> Publications


DBLP | ACM DL | Google Scholar | BibTeX


    2014


  1. Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
    ArXiv, abs/1311.3048, 2013
    [
    url
    ]
    STOC, 2014
    [
    ]
    (with Ittai Abraham, Cyril Gavoille, Ofer Neiman, and Kunal Talwar)
  2. Minimum d-dimensional arrangement with fixed points
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1307.6627, 2013
    [
    url
    ]
    (with Anastasios Sidiropoulos)
  3. Towards $(1+\epsilon)$-Approximate Flow Sparsifiers
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1310.3252, 2013
    [
    url
    ]
    (with Alexandr Andoni and Robert Krauthgamer)
  4. Online Steiner Tree with Deletions
    SODA, 2014
    [
    doi
    ]
    ArXiv, 1312.7296, 2014
    [
    url
    ]
    (with Amit Kumar)
  5. Maintaining Assignments Online: Matching, Scheduling, and Flows
    SODA, 2014
    [
    doi
    ]
    (with Amit Kumar and Cliff Stein)
  6. Changing Bases: Multistage Optimization for Matroids and Matchings
    ArXiv, 1404.3768, 2014
    [
    url
    ]
    ICALP, 2014
    [
    ]
    (with Kunal Talwar and Udi Wieder)


  7. 2013


  8. Random Rates for 0-Extension and Low-Diameter Decompositions
    ArXiv, 1307.5582, 2013
    [
    url
    ]
    (with Kunal Talwar)
  9. Harnessing the Power of Two Crossmatches
    14th ACM Conference on Electronic Commerce, 2013
    [
    doi
    ]
    (with Avrim Blum, Ariel Procaccia, and Ankit Sharma)
  10. Algorithms for Hub Label Optimization
    ICALP, 2013
    [
    doi
    ]
    (with Maxim Babenko, Andrew V. Goldberg, and Viswanath Nagarajan)
  11. The Approximability of the Binary Paintshop Problem
    APPROX-RANDOM, 2013
    [
    doi
    ]
    (with Satyen Kale, Viswanath Nagarajan, Rishi Saket, and Baruch Schieber)
  12. The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
    STOC, 2013
    [ ]
    ArXiv, abs/1307.3757, 2013
    [
    url
    ]
    (with Albert Gu and Amit Kumar)
  13. On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
    STOC, 2013
    [
    doi
    ]
    ArXiv, 1305.1347, 2013
    [
    url
    ]
    (with Kunal Talwar and David Witmer)
  14. Thrifty Algorithms for Multistage Robust Optimization
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5445, 2013
    [
    url
    ]
    (with Viswanath Nagarajan and Vijay V. Vazirani)
  15. A Stochastic Probing Problem with Applications
    IPCO, 2013
    [
    doi
    ]
    ArXiv, 1302.5913, 2013
    [
    url
    ]
    (with Viswanath Nagarajan)
  16. Packing Interdiction and Partial Covering Problems
    IPCO, 2013
    [
    doi
    ]
    (with Michael Dinitz)
  17. An Improved Integrality Gap for Asymmetric TSP Paths
    IPCO, 2013
    [
    doi
    ]
    ArXiv, abs/1302.3145, 2013
    [
    url
    ]
    (with Zachary Friggstad and Mohit Singh)
  18. Catch Them If You Can: How to Serve Impatient Users
    Innovations in Theoretical Computer Science Conference, 2013
    [ ]
    (with Marek Cygan, Matthias Englert, Marcin Mucha, and Piotr Sankowski)


  19. 2012


  20. Multicast Routing for Energy Minimization Using Speed Scaling
    First Mediterranean Conference on Algorithms (MedAlg), 2012
    [
    doi
    ]
    (with Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, and Cliff Stein)
  21. Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
    ArXiv, abs/1109.5931, 2011
    [
    url
    ]
    Workshop on Approximation and Online Algorithms, 2012
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  22. Parallel Probabilistic Tree Embeddings, k-Median, and Buy-at-Bulk Network Design
    SPAA, 2012
    [
    doi
    ]
    (with Guy E. Blelloch and Kanat Tangwongsan)
  23. The Online Metric Matching Problem for Doubling Metrics
    ICALP (1), 2012
    [
    doi
    ]
    (with Kevin Lewi)
  24. Approximating Sparse Covering Integer Programs Online
    ArXiv, abs/1205.0175, 2012
    [
    url
    ]
    ICALP (1), 2012
    [
    doi
    ]
    (with Viswanath Nagarajan)
  25. Iterative Constructions and Private Data Release
    ArXiv, abs/1107.3731, 2011
    [
    url
    ]
    TCC, 2012
    [
    doi
    ]
    (with Aaron Roth and Jonathan Ullman)
  26. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    SODA, 2012
    [
    url
    ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
  27. Approximation Algorithms for Stochastic Orienteering
    SODA, 2012
    [
    url
    ]
    (with Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi)
  28. Approximation Algorithms for VRP with Stochastic Demands
    Operations Research, 60(1):2012
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)


  29. 2011


  30. Welfare and Profit Maximization with Production Costs
    ArXiv, abs/1110.4992, 2011
    [
    url
    ]
    FOCS, 2011
    [
    doi
    ]
    (with Avrim Blum, Yishay Mansour, and Ankit Sharma)
  31. Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
    ArXiv, abs/1102.3749, 2011
    [
    url
    ]
    FOCS, 2011
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi)
  32. Privately Releasing Conjunctions and the Statistical Query Barrier
    ArXiv, abs/1011.1296, 2010
    [
    url
    ]
    SIAM J. Comput., 42(4):2013
    [
    doi
    ]
    STOC, 2011
    [
    doi
    ]
    (with Moritz Hardt, Aaron Roth, and Jonathan Ullman)
  33. Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
    Theory of Computing Systems (Special Issue for SPAA 2011 papers), 2013
    [
    doi
    ]
    SPAA, 2011
    [
    doi
    ]
    (with Guy E. Blelloch, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat Tangwongsan)
  34. Approximation algorithms for network design: A survey
    Surveys in Operations Research and Management Science, 16(1):2011
    [ ]
    (with Jochen Könemann)


  35. 2010


  36. Discovering pathways by orienting edges in protein interaction networks.
    Nucleic Acids Res, 2010
    [
    doi
    ]
    (with Anthony Gitter, Judith Klein-Seetharaman, and Ziv Bar-Joseph)
  37. Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms
    WINE, 2010
    [
    doi
    ]
    ArXiv, abs/1003.1517, 2010
    [
    url
    ]
    (with Aaron Roth, Grant Schoenebeck, and Kunal Talwar)
  38. Coordinated Sampling sans Origin-Destination Identifiers: Algorithms, Analysis, and Evaluation
    IEEE Communication Systems and Networks (COMSNETS), 2010
    [
    doi
    ]
    (with Vyas Sekar, Michael K. Reiter, and Hui Zhang)
  39. Network-Wide Deployment of Intrusion Detection and Prevention Systems
    ACM CoNEXT, 2010
    [ ]
    (with Vyas Sekar, Ravishankar Krishnaswamy, and Michael K. Reiter)
  40. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
    ESA (2), 2010
    [
    doi
    ]
    Algorithmica, 63(4):2012
    [
    doi
    ]
    ArXiv, abs/1008.5356, 2010
    [
    url
    ]
    (with Nikhil Bansal, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra)
  41. Scalably Scheduling Power-Heterogeneous Processors
    ICALP (1), 2010
    [
    doi
    ]
    ArXiv, abs/1105.3748, 2011
    [
    url
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  42. Improved Approximation Algorithms for Requirement Cut
    Operations Research Letters, 38(4):2010
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)
  43. A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
    SODA, 2010
    [
    doi
    ]
    (with Nikhil Bansal and Ravishankar Krishnaswamy)
  44. Scheduling jobs with varying parallelizability to reduce variance
    SPAA, 2010
    [ ]
    (with Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs)
  45. Nonclairvoyantly scheduling power-heterogeneous processors
    International Green Computing Conference, 2010
    [ ]
    Sustainable Computing: Informatics and Systems, 1(3):2011
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and Kirk Pruhs)
  46. Forest Density Estimation
    COLT, 2010
    [
    url
    ]
    Journal of Machine Learning Research, 12, 2011
    [
    url
    ]
    ArXiv, abs/1001.1557, 2010
    [
    url
    ]
    (with John Lafferty, Han Liu, Larry Wasserman, and Min Xu)
  47. Vertex Sparsifiers: New Results from Old Techniques
    APPROX-RANDOM, 2010
    [
    doi
    ]
    ArXiv, abs/1006.4586, 2010
    [
    url
    ]
    (with Matthias Englert, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar)
  48. Tree Embeddings for Two-Edge-Connected Network Design
    SODA, 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and R. Ravi)
  49. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
    ArXiv, abs/1003.0722, 2010
    [
    url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi)


  50. 2009


  51. Secretary problems: weights and discounts
    SODA, 2009
    [ ]
    (with Moshe Babaioff, Michael Dinitz, Nicole Immorlica, and Kunal Talwar)
  52. Scheduling with Outliers
    ArXiv, abs/0906.2020, 2009
    [
    url
    ]
    APPROX, 2009
    [
    doi
    ]
    (with Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev)
  53. Simultaneous placement and scheduling of sensors
    IPSN, 2009
    [
    doi
    ]
    IEEE Transactions on Automatic Control, 56(10):2011
    [
    doi
    ]
    (with Andreas Krause, Ram Rajagopal, and Carlos Guestrin)
  54. A constant-factor approximation for stochastic Steiner forest
    STOC, 2009
    [ ]
    (with Amit Kumar)
  55. Approximate clustering without the approximation
    SODA, 2009
    [ ]
    JACM, 60(2):2013
    [
    doi
    ]
    (with Maria-Florina Balcan and Avrim Blum)
  56. Online and stochastic survivable network design
    STOC, 2009
    [ ]
    SIAM J. Comput., 41(6):2012
    [
    doi
    ]
    (with Ravishankar Krishnaswamy and R. Ravi)
  57. Thresholded Covering Algorithms for Robust and Max-Min Optimization
    ArXiv, abs/0912.1045, 2009
    [
    url
    ]
    ArXiv, abs/1012.4962, 2010
    [
    url
    ]
    ICALP (1), 2010
    [
    doi
    ]
    (with Viswanath Nagarajan and R. Ravi)
  58. Differentially Private Approximation Algorithms
    ArXiv, abs/0903.4510, 2009
    [
    url
    ]
    SODA, 2010
    [
    doi
    ]
    (with Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar)


  59. 2008


  60. Approximating TSP on metrics with bounded global growth
    SODA, 2008
    [ ]
    SIAM Journal on Computing, 41(3):2012
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  61. Set connectivity problems in undirected graphs and the directed Steiner network problem
    SODA, 2008
    [ ]
    ACM Transactions on Algorithms, 7(2):2011
    [
    doi
    ]
    (with Chandra Chekuri, Guy Even, and Danny Segev)
  62. A plant location guide for the unsure
    SODA, 2008
    [ ]
    Math. Oper. Res., 35(1):2010
    [ ]
    (with Barbara M. Anthony, Vineet Goyal, and Viswanath Nagarajan)
  63. Ultra-low-dimensional embeddings for doubling metrics
    SODA, 2008
    [ ]
    J. ACM, 57(4):2010
    [
    doi
    ]
    (with T.-H. Hubert Chan and Kunal Talwar)
  64. Simpler Analyses of Local Search Algorithms for Facility Location
    ArXiv, abs/0809.2554, 2008
    [
    url
    ]
    (with Kanat Tangwongsan)
  65. Extracting Dynamics from Static Cancer Expression Data
    IEEE/ACM Trans. Comput. Biol. Bioinformatics, 5(2):2008
    [
    doi
    ]
    (with Ziv Bar-Joseph)
  66. All-Norms and All-$L_p$-Norms Approximation Algorithms
    FST&TCS, 2008
    [ ]
    (with Daniel Golovin, Amit Kumar, and Kanat Tangwongsan)
  67. Set Covering with our Eyes Closed
    FOCS, 2008
    [ ]
    SIAM J. Comput., 42(3):2013
    [ ]
    (with Fabrizio Grandoni, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh)
  68. Selecting Observations against Adversarial Objectives
    Advances in Neural Information Processing Systems 20, 2008
    [
    url
    ]
    Journal of Machine Learning Research, 9, 2008
    [
    url
    ]
    (with Andreas Krause, Brendan McMahan, and Carlos Guestrin)
  69. Stochastic analyses for online combinatorial optimization problems
    SODA, 2008
    [ ]
    (with Naveen Garg, Stefano Leonardi, and Piotr Sankowski)


  70. 2007


  71. An $O(\log^2 k)$-Competitive Algorithm for Metric Bipartite Matching
    ESA, 2007
    [ ]
    Algorithmica, 68(2):2014
    [
    doi
    ]
    (with Nikhil Bansal, Niv Buchbinder, and Joseph Naor)
  72. Pricing Tree Access Networks with Connected Backbones
    ESA, 2007
    [ ]
    (with Vineet Goyal, Stefano Leonardi, and R. Ravi)
  73. On Configuring BGP Route Reflectors
    2nd International Conference on COMmunication System softWAre and MiddlewaRE (COMSWARE), 2007
    [
    doi
    ]
    (with Yuri Breitbart, Minos N. Garofalakis, Amit Kumar, and Rajeev Rastogi)
  74. Infrastructure Leasing Problems
    IPCO, 2007
    [ ]
    (with Barbara M. Anthony)
  75. An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem
    SODA, 2007
    [ ]
    Mathematical Programming, 2014
    [
    url
    ]
    (with Jochen Könemann, Stefano Leonardi, R. Ravi, and Guido Schäfer)
  76. How to Complete a Doubling Metric
    ArXiv, abs/0712.3331, 2007
    [
    url
    ]
    LATIN, 2008
    [
    doi
    ]
    Algorithmica, 59(1):2011
    [
    doi
    ]
    (with Kunal Talwar)
  77. Stochastic Steiner Tree with Non-Uniform Inflation
    APPROX, 2007
    [ ]
    (with MohammadTaghi Hajiaghayi and Amit Kumar)
  78. Dial a Ride from k-forest
    ArXiv, abs/0707.0648, 2007
    [
    url
    ]
    ACM Transactions on Algorithms, 6(2):2010
    [
    doi
    ]
    ESA, 2007
    [
    doi
    ]
    (with MohammadTaghi Hajiaghayi, Viswanath Nagarajan, and R. Ravi)


  79. 2006


  80. Near-optimal sensor placements: maximizing information while minimizing communication cost
    Conference on Information Processing in Sensor Networks, 2006
    [
    doi
    ]
    ACM Transactions on Sensor Networks, 7(4):2011
    [
    doi
    ]
    (with Andreas Krause, Carlos Guestrin, and Jon M. Kleinberg)
  81. Quorum placement in networks: minimizing network congestion
    PODC, 2006
    [ ]
    (with Daniel Golovin, Bruce M. Maggs, Florian Oprea, and Michael K. Reiter)
  82. Approximating unique games
    SODA, 2006
    [ ]
    (with Kunal Talwar)
  83. Spanners with Slack
    ESA, 2006
    [ ]
    (with T.-H. Hubert Chan and Michael Dinitz)
  84. Small hop-diameter sparse spanners for doubling metrics
    SODA, 2006
    [ ]
    Discrete & Computational Geometry, 41(1):2009
    [
    doi
    ]
    (with T.-H. Hubert Chan)
  85. Oblivious network design
    SODA, 2006
    [ ]
    (with MohammadTaghi Hajiaghayi and Harald Räcke)
  86. Improved embeddings of graph metrics into random trees (article withdrawn)
    SODA, 2006
    [
    doi
    ]
    (with Kedar Dhamdhere and Harald Räcke)


  87. 2005


  88. On the Approximability of Network Design Problems
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Julia Chuzhoy, Joseph (Seffi) Naor, and Amitabh Sinha)
  89. Metric Embeddings with Relaxed Guarantees
    FOCS, 2005
    [ ]
    SIAM Journal on Computing, 38(6):2009
    [
    doi
    ]
    (with Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Jon M. Kleinberg, Ofer Neiman, and Aleksandrs Slivkins)
  90. Stochastic Steiner Trees Without a Root
    ICALP, 2005
    [ ]
    (with Martin Pál)
  91. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization
    APPROX, 2005
    [ ]
    (with Martin Pál, R. Ravi, and Amitabh Sinha)
  92. Approximation Algorithms for Embeddings Into Low-Dimensional Spaces
    SODA, 2005
    [ ]
    (with Mihai B\uadoiu, Kedar Dhamdhere, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos)
  93. Quorum placement in networks to minimize access delays
    PODC, 2005
    [ ]
    (with Bruce M. Maggs, Florian Oprea, and Michael K. Reiter)
  94. Where's the Winner? Max-Finding and Sorting with Metric Costs
    APPROX, 2005
    [ ]
    (with Amit Kumar)
  95. Improved Approximations for Sparsest {Cut}
    SODA, 2005
    [ ]
    ACM Trans. Algorithms, 4(2):2008
    [
    doi
    ]
    (with Shuchi Chawla and Harald Räcke)
  96. On Hierarchical Routing in Doubling Metrics
    SODA, 2005
    [ ]
    (with T.-H. Hubert Chan, Bruce M. Maggs, and Shuheng Zhou)
  97. On a bidirected relaxation for the Multiway {Cut} problem
    Discrete Appl. Math., 150(1-3):2005
    [
    doi
    ]
    (with Chandra Chekuri and Amit Kumar)


  98. 2004


  99. Cost-Sharing Mechanisms for Network Design.
    APPROX, 2004
    [ ]
    Algorithmica, 50(1):2008
    [
    doi
    ]
    (with Aravind Srinivasan and \'Eva Tardos)
  100. Approximation Algorithms for Minimizing Average Distortion
    STACS, 2004
    [ ]
    Theory of Computing Systems, 39(1):2006
    [
    doi
    ]
    (with Kedar Dhamdhere and R. Ravi)
  101. Boosted Sampling: Approximation algorithms for stochastic optimization problems
    STOC, 2004
    [ ]
    SIAM J. Comput., 40(5):2011
    [
    doi
    ]
    (with Martin Pál, R. Ravi, and Amitabh Sinha)
  102. An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
    FOCS, 2004
    [ ]
    Mathematics of Operations Research, 32(2):2007
    [
    doi
    ]
    (with R. Ravi and Amitabh Sinha)


  103. 2003


  104. Exploring the Trade-off between Label Size and Stack Depth in MPLS Routing
    INFOCOM, 2003
    [
    ]
    (with Amit Kumar and Rajeev Rastogi)
  105. Bounded geometries, fractals, and low--distortion embeddings
    FOCS, 2003
    [ ]
    (with Robert Krauthgamer and James R.\ Lee)
  106. Approximations via Cost-Sharing
    FOCS, 2003
    [ ]
    J. ACM, 54(3):2007
    [
    doi
    ]
    (with Amit Kumar, Martin Pál, and Tim Roughgarden)
  107. Improved Approximations for Directed Multicut
    SODA, 2003
    [ ]
  108. On the Covering {Steiner} Problem
    FST&TCS, 2003
    [ ]
    Theory of Computing, 2, 2006
    [
    doi
    ]
    (with Aravind Srinivasan)
  109. Lower Bounds for Embedding Edit Distance into Normed Spaces
    SODA, 2003
    [ ]
    (with Alexandr Andoni, Michel Marie Deza, Piotr Indyk, and Sofya Raskhodnikova)
  110. Tree based MPLS routing
    SPAA, 2003
    [
    doi
    ]
    (with Amit Kumar and Mikkel Thorup)
  111. Embedding $k$-outerplanar graphs into $\ell_1$
    SODA, 2003
    [ ]
    SIAM J. Discrete Math., 20(1):2006
    [
    doi
    ]
    (with Chandra Chekuri, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair)
  112. Counting Inversions in Lists
    SODA, 2003
    [ ]
    (with Francis X. Zane)
  113. Simpler and Better Approximation Algorithms for Network Design
    STOC, 2003
    [ ]
    (with Amit Kumar and Tim Roughgarden)


  114. 2002


  115. Building edge-failure resilient networks
    IPCO, 2002
    [ ]
    Algorithmica, 43(1-2):2005
    [
    doi
    ]
    (with Chandra Chekuri, Amit Kumar, Joseph (Seffi) Naor, and Danny Raz)
  116. A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem
    FOCS, 2002
    [ ]
    (with Amit Kumar and Tim Roughgarden)
  117. Approximation Algorithms for Unsplittable Flow Problems
    APPROX, 2002
    [ ]
    Algorithmica, 47(1):2007
    [
    doi
    ]
    (with Amit Chakrabarti, Chandra Chekuri, and Amit Kumar)


  118. 2001


  119. Provisioning a Virtual Private Network: {A} Network Design Problem for Multicommodity Flow
    STOC, 2001
    [ ]
    (with Amit Kumar, Jon M. Kleinberg, Rajeev Rastogi, and Bülent Yener)
  120. Traveling with a Pez dispenser (or, routing issues in {MPLS})
    FOCS, 2001
    [ ]
    SIAM J. Comput., 34(2):2004
    [
    doi
    ]
    (with Amit Kumar and Rajeev Rastogi)
  121. Sorting and selection with structured costs
    FOCS, 2001
    [ ]
    (with Amit Kumar)
  122. Steiner points in tree metrics don't (really) help
    SODA, 2001
    [ ]


  123. 2000


  124. A Constant Factor Approximation Algorithm for a Class of Classification Problems
    STOC, 2000
    [ ]
    (with \'Eva Tardos)
  125. Improved bandwidth approximation for trees
    SODA, 2000
    [ ]
    J. Algorithms, 40(1):2001
    [
    doi
    ]
  126. Embeddings of Finite Metrics
    Ph.D. Thesis, University of California, Berkeley, 2000
    [
    ]


  127. 1999


  128. Cuts, trees and $\ell_1$-embeddings of graphs
    FOCS, 1999
    [ ]
    Combinatorica, 24(2):2004
    [
    doi
    ]
    (with Ilan Newman, Yuri Rabinovich, and Alistair Sinclair)
  129. Embedding tree metrics into low dimensional Euclidean spaces
    STOC, 1999
    [ ]
    Discrete Comput. Geom., 24(1):2000
    [
    doi
    ]
  130. A simple proof of the Johnson-Lindenstrauss lemma
    Tech report, International Computer Science Institute, 1999
    [
    url
    ]
    Random Structures Algorithms, 22(1):2003
    [ ]
    (with Sanjoy Dasgupta)

Designed by Kanat Tangwongsan, mildly altered by AG.
Last updated: 2014-05-09.