dblp.uni-trier.dewww.uni-trier.de

Satish Rao

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2009
97EESanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): (2009)
2008
96EEKamalika Chaudhuri, Satish Rao: Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions. COLT 2008: 21-32
95EEKamalika Chaudhuri, Satish Rao: Learning Mixtures of Product Distributions Using Correlations and Independence. COLT 2008: 9-20
94EEPunyashloka Biswal, James R. Lee, Satish Rao: Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. FOCS 2008: 751-760
93EEJittat Fakcharoenphol, Satish Rao, Kunal Talwar: Approximating Metric Spaces by Tree Metrics. Encyclopedia of Algorithms 2008
92EEJittat Fakcharoenphol, Satish Rao: Shortest Paths in Planar Graphs with Negative Weight Edges. Encyclopedia of Algorithms 2008
91EEPunyashloka Biswal, James R. Lee, Satish Rao: Eigenvalue bounds, spectral partitioning, and metrical deformations via flows CoRR abs/0808.0148: (2008)
90EERadu Mihaescu, Cameron Hill, Satish Rao: Fast phylogeny reconstruction through learning of ancestral sequences CoRR abs/0812.1587: (2008)
89EESanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)
88EESagi Snir, Tandy Warnow, Satish Rao: Short Quartet Puzzling: A New Quartet-Based Phylogeny Reconstruction Algorithm. Journal of Computational Biology 15(1): 91-103 (2008)
2007
87EESrinath Sridhar, Satish Rao, Eran Halperin: An Efficient and Accurate Graph-Based Approach to Detect Population Substructure. RECOMB 2007: 503-517
86EEKamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou: A rigorous analysis of population stratification with limited data. SODA 2007: 1046-1055
85EEBaruch Awerbuch, Rohit Khandekar, Satish Rao: Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. SODA 2007: 949-957
84EEJittat Fakcharoenphol, Chris Harrelson, Satish Rao: The k-traveling repairmen problem. ACM Transactions on Algorithms 3(4): (2007)
83EEStavros G. Kolliopoulos, Satish Rao: A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem. SIAM J. Comput. 37(3): 757-782 (2007)
2006
82EEKamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: A Push-Relabel Algorithm for Approximating Degree Bounded MSTs. ICALP (1) 2006: 191-201
81EESatish Rao, Shuheng Zhou: Edge Disjoint Paths in Moderately Connected Graphs. ICALP (1) 2006: 202-213
80EEConstantinos Daskalakis, Cameron Hill, Alexander Jaffe, Radu Mihaescu, Elchanan Mossel, Satish Rao: Maximal Accurate Forests from Distance Matrices. RECOMB 2006: 281-295
79EEMoses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao: l22 spreading metrics for vertex ordering problems. SODA 2006: 1018-1027
78EEKamalika Chaudhuri, Kevin Chen, Radu Mihaescu, Satish Rao: On the tandem duplication-random loss model of genome rearrangement. SODA 2006: 564-570
77EERohit Khandekar, Satish Rao, Umesh V. Vazirani: Graph partitioning using single commodity flows. STOC 2006: 385-390
76EESagi Snir, Satish Rao: Using Max Cut to Enhance Rooted Trees Consistency. IEEE/ACM Trans. Comput. Biology Bioinform. 3(4): 323-333 (2006)
75EEJittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)
2005
74EEKamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. APPROX-RANDOM 2005: 26-39
73EEAbraham Bachrach, Kevin Chen, Chris Harrelson, Radu Mihaescu, Satish Rao, Apurva Shah: Lower Bounds for Maximum Parsimony with Gene Order Data. Comparative Genomics 2005: 1-10
72EEShlomo Moran, Satish Rao, Sagi Snir: Using Semi-definite Programming to Enhance Supertree Resolvability. WABI 2005: 89-103
2004
71EEKevin Lang, Satish Rao: A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. IPCO 2004: 325-337
70EEKirsten Hildrum, Sean Ma, Satish Rao: Brief announcement: randomized rumor spreading with fewer phone calls. PODC 2004: 380
69EEKirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao: A note on the nearest neighbor in growth-restricted metrics. SODA 2004: 560-561
68EESanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231
67EEJittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3): 485-497 (2004)
66EESatish Rao, Andréa W. Richa: New Approximation Techniques for Some Linear Ordering Problems. SIAM J. Comput. 34(2): 388-404 (2004)
65EEJittat Fakcharoenphol, Satish Rao, Kunal Talwar: Approximating metrics by tree metrics. SIGACT News 35(2): 60-70 (2004)
2003
64EEKamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar: Paths, Trees, and Minimum Latency Tours. FOCS 2003: 36-45
63EEJittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar: An improved approximation algorithm for the 0-extension problem. SODA 2003: 257-265
62EEJittat Fakcharoenphol, Chris Harrelson, Satish Rao: The k-traveling repairman problem. SODA 2003: 655-664
61EEChris Harrelson, Kirsten Hildrum, Satish Rao: A polynomial-time tree decomposition to minimize congestion. SPAA 2003: 34-43
60EEJittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003: 448-455
59EEEyal Amir, Robert Krauthgamer, Satish Rao: Constant factor approximation of vertex-cuts in planar graphs. STOC 2003: 90-99
2002
58EEKirsten Hildrum, John Kubiatowicz, Satish Rao, Ben Y. Zhao: Distributed object location in a dynamic network. SPAA 2002: 41-52
2001
57 Jittat Fakcharoenphol, Satish Rao: Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. FOCS 2001: 232-241
56EEFrank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan: New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SIAM J. Comput. 31(2): 626-641 (2001)
2000
55EEMark W. Goudreau, Stavros G. Kolliopoulos, Satish Rao: Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation. INFOCOM 2000: 1624-1643
54EEGuy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4): 585-616 (2000)
53 Monika Rauch Henzinger, Satish Rao, Harold N. Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques. J. Algorithms 34(2): 222-250 (2000)
1999
52EEStavros G. Kolliopoulos, Satish Rao: A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem. ESA 1999: 378-389
51EEFrank Thomson Leighton, Satish Rao, Aravind Srinivasan: New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA 1999: 643-652
50EEMark W. Goudreau, Kevin Lang, Girija J. Narlikar, Satish Rao: BOS is Boss: A Case for Bulk-Synchronous Object Systems. SPAA 1999: 115-125
49EESatish Rao: Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics. Symposium on Computational Geometry 1999: 300-306
48 Mark W. Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas: Portable and Efficient Parallel Computing Using the BSP Model. IEEE Trans. Computers 48(7): 670-689 (1999)
47EEFrank Thomson Leighton, Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6): 787-832 (1999)
46 Leslie Ann Goldberg, Yossi Matias, Satish Rao: An Optical Simulation of Shared Memory. SIAM J. Comput. 28(5): 1829-1847 (1999)
45 Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6): 2187-2214 (1999)
44EEAndrew V. Goldberg, Satish Rao: Flows in Undirected Unit Capacity Networks. SIAM J. Discrete Math. 12(1): 1-5 (1999)
1998
43 Satish Rao, Andréa W. Richa: New Approximation Techniques for Some Ordering Problems. SODA 1998: 211-218
42EESanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation Schemes for Euclidean k-Medians and Related Problems. STOC 1998: 106-113
41EESatish Rao, Warren D. Smith: Approximating Geometrical Graphs via "Spanners" and "Banyans". STOC 1998: 540-550
40EEAndrew V. Goldberg, Satish Rao: Beyond the Flow Decomposition Barrier. J. ACM 45(5): 783-797 (1998)
39EEJonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas, Rob H. Bisseling: BSPlib: The BSP programming library. Parallel Computing 24(14): 1947-1980 (1998)
1997
38EEAndrew V. Goldberg, Satish Rao: Beyond the Flow Decomposition Barrier. FOCS 1997: 2-11
37EEAndrew V. Goldberg, Satish Rao: Flows in Undirected Unit Capacity Networks. FOCS 1997: 32-34
36 Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Spreading Metric Based Graph Partitioning Algorithms. PPSC 1997
35 Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SODA 1997: 639-648
34EERichard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg, Eric J. Schwabe: Work-preserving emulations of fixed-connection networks. J. ACM 44(1): 104-147 (1997)
33 Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos: Approximation Algorithms for Steiner and Directed Multicuts. J. Algorithms 22(2): 241-269 (1997)
32 Charles E. Leiserson, Satish Rao, Sivan Toledo: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers. J. Comput. Syst. Sci. 54(2): 332-344 (1997)
31 Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian: Faster Shortest-Path Algorithms for Planar Graphs. J. Comput. Syst. Sci. 55(1): 3-23 (1997)
30 Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao: Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM J. Comput. 26(4): 1100-1119 (1997)
29 Johnny Wong, Satish Rao, Naveen Ramaiah: A Multimedia Presentation Toolkit for the World Wide Web. Softw., Pract. Exper. 27(4): 425-446 (1997)
28 Christos Kaklamanis, Danny Krizanc, Satish Rao: New Graph Decompositions with Applications to Emulations. Theory Comput. Syst. 30(1): 39-49 (1997)
1996
27 Monika Rauch Henzinger, Satish Rao, Harold N. Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques. FOCS 1996: 462-471
26 Mark W. Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas: Towards Efficiency and Portability: Programming with the BSP Model. SPAA 1996: 1-12
25EEIngemar J. Cox, Sunita L. Hingorani, Satish Rao, Bruce M. Maggs: A Maximum Likelihood Stereo Algorithm. Computer Vision and Image Understanding 63(3): 542-567 (1996)
1995
24 Milena Mihail, Christos Kaklamanis, Satish Rao: Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings. FOCS 1995: 548-557
23 Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). FOCS 1995: 62-71
22EESatish Rao, Torsten Suel, Thanasis Tsantilas, Mark W. Goudreau: Efficient communication using total-exchange. IPPS 1995: 544-550
21 Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi: An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. Combinatorica 15(2): 187-202 (1995)
1994
20 Serge A. Plotkin, Satish Rao, Warren D. Smith: Shallow Excluded Minors and Improved Graph Decompositions. SODA 1994: 462-470
19EELeslie Ann Goldberg, Yossi Matias, Satish Rao: An Optical Simulation of Shared Memory. SPAA 1994: 257-267
18EEPhilip N. Klein, Satish Rao, Monika Rauch Henzinger, Sairam Subramanian: Faster shortest-path algorithms for planar graphs. STOC 1994: 27-37
17 Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14(2): 167-186 (1994)
16 Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, Satish Rao: Randomized Routing and Sorting on Fixed-Connection Networks. J. Algorithms 17(1): 157-205 (1994)
1993
15 Christos Kaklamanis, Danny Krizanc, Satish Rao: Universal Emulations with Sublogarithmic Slowdown FOCS 1993: 341-350
14 Charles E. Leiserson, Satish Rao, Sivan Toledo: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract) FOCS 1993: 704-713
13 Kevin Lang, Satish Rao: Finding Near-Optimal Cuts: An Empirical Evaluation. SODA 1993: 212-221
12EELeslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao: A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer. SPAA 1993: 300-309
11EEChristos Kaklamanis, Danny Krizanc, Satish Rao: New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies. SPAA 1993: 325-334
10EEWilliam Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao: Approximate load balancing on dynamic and asynchronous networks. STOC 1993: 632-641
9EEPhilip N. Klein, Serge A. Plotkin, Satish Rao: Excluded minors, network decomposition, and multicommodity flow. STOC 1993: 682-690
1992
8EEChristos Kaklamanis, Danny Krizanc, Satish Rao: Simple Path Selection for Optimal Routing on Processor Arrays. SPAA 1992: 23-30
7 Satish Rao: Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract) STOC 1992: 229-240
1990
6 Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas: Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract) FOCS 1990: 285-296
5 Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao: Approximation through Multicommodity Flow FOCS 1990: 726-737
1989
4 Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg: Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract) STOC 1989: 227-240
1988
3 Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Universal Packet Routing Algorithms (Extended Abstract) FOCS 1988: 256-269
2 Frank Thomson Leighton, Satish Rao: An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms FOCS 1988: 422-431
1987
1 Satish Rao: Finding Near Optimal Separators in Planar Graphs FOCS 1987: 225-237

Coauthor Index

1Ajit Agrawal [5] [21]
2William Aiello [10]
3Eyal Amir [59]
4Sanjeev Arora [42] [68] [89] [97]
5Baruch Awerbuch [10] [85]
6Abraham Bachrach [73]
7Rob H. Bisseling [39]
8Punyashloka Biswal [91] [94]
9Moses Charikar [79]
10Kamalika Chaudhuri [64] [74] [78] [82] [86] [95] [96]
11Kevin Chen [73] [78]
12Ingemar J. Cox [25]
13Constantinos Daskalakis (Konstantinos Daskalakis) [80]
14Guy Even [23] [35] [36] [45] [54]
15Jittat Fakcharoenphol [57] [60] [62] [63] [65] [67] [75] [84] [92] [93]
16Harold N. Gabow [27] [53]
17Brighten Godfrey [64]
18Andrew V. Goldberg [37] [38] [40] [44]
19Leslie Ann Goldberg [12] [19] [30] [46]
20Mark W. Goudreau [22] [26] [39] [48] [50] [55]
21Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi) [79]
22Eran Halperin [86] [87]
23Chris Harrelson [61] [62] [63] [73] [84]
24Monika Rauch Henzinger (Monika Rauch) [18] [27] [31] [53]
25Kirsten Hildrum (Kris Hildrum) [58] [61] [69] [70]
26Cameron Hill [80] [90]
27Jonathan M. D. Hill [39]
28Sunita L. Hingorani [25]
29Alexander Jaffe [80]
30Mark Jerrum [12] [30]
31Christos Kaklamanis [6] [8] [11] [15] [24] [28]
32Anna R. Karlin [6]
33Howard J. Karloff [79]
34Rohit Khandekar [77] [85]
35Philip N. Klein [5] [9] [18] [21] [31] [33]
36Richard R. Koch [4] [34]
37Stavros G. Kolliopoulos [52] [55] [83]
38Robert Krauthgamer [59]
39Danny Krizanc [8] [11] [15] [28]
40John Kubiatowicz [58] [69]
41Kevin Lang [13] [26] [39] [48] [50] [71]
42James R. Lee [91] [94]
43Frank Thomson Leighton (Tom Leighton) [2] [3] [4] [6] [12] [16] [17] [30] [34] [47] [51] [56]
44Charles E. Leiserson [14] [32]
45Chi-Jen Lu [56]
46Sean Ma [69] [70]
47Bruce M. Maggs [3] [4] [10] [16] [17] [25] [34]
48Yossi Matias [19] [46]
49Bill McColl [39]
50Radu Mihaescu [73] [78] [80] [90]
51Milena Mihail [24]
52Victor J. Milenkovic (Victor Milenkovic) [6]
53Shlomo Moran [72]
54Elchanan Mossel [80]
55Joseph Naor (Seffi Naor) [23] [35] [36] [45] [54]
56Girija J. Narlikar [50]
57Serge A. Plotkin [9] [20] [33]
58Prabhakar Raghavan [6] [42]
59Naveen Ramaiah [29]
60Abhiram G. Ranade [16]
61R. Ravi [5] [21]
62Andréa W. Richa [43] [66]
63Samantha Riesenfeld [74] [82]
64Arnold L. Rosenberg [4] [34]
65Baruch Schieber [23] [35] [36] [45] [54]
66Eric J. Schwabe [34]
67Apurva Shah [73]
68Warren D. Smith [20] [41]
69Sagi Snir [72] [76] [88]
70Srinath Sridhar [87]
71Aravind Srinivasan [51] [56]
72Dan C. Stefanescu [39]
73Sairam Subramanian [18] [31]
74Torsten Suel [22] [26] [39] [48]
75Kunal Talwar [60] [63] [64] [65] [67] [74] [82] [93]
76Éva Tardos [33]
77Clark D. Thomborson (Clark D. Thompson) [6]
78Sivan Toledo [14] [32]
79A. Tsantilas [6]
80Thanasis Tsantilas [22] [26] [39] [48]
81Umesh V. Vazirani [68] [77] [89] [97]
82Tandy Warnow [88]
83Johnny S. Wong (Johnny Wong) [29]
84Ben Y. Zhao [58]
85Shuheng Zhou [81] [86]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)