| 2009 |
|---|
| 97 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning.
J. ACM 56(2): (2009) |
| 2008 |
|---|
| 96 | EE | Kamalika Chaudhuri,
Satish Rao:
Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions.
COLT 2008: 21-32 |
| 95 | EE | Kamalika Chaudhuri,
Satish Rao:
Learning Mixtures of Product Distributions Using Correlations and Independence.
COLT 2008: 9-20 |
| 94 | EE | Punyashloka Biswal,
James R. Lee,
Satish Rao:
Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows.
FOCS 2008: 751-760 |
| 93 | EE | Jittat Fakcharoenphol,
Satish Rao,
Kunal Talwar:
Approximating Metric Spaces by Tree Metrics.
Encyclopedia of Algorithms 2008 |
| 92 | EE | Jittat Fakcharoenphol,
Satish Rao:
Shortest Paths in Planar Graphs with Negative Weight Edges.
Encyclopedia of Algorithms 2008 |
| 91 | EE | Punyashloka Biswal,
James R. Lee,
Satish Rao:
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
CoRR abs/0808.0148: (2008) |
| 90 | EE | Radu Mihaescu,
Cameron Hill,
Satish Rao:
Fast phylogeny reconstruction through learning of ancestral sequences
CoRR abs/0812.1587: (2008) |
| 89 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Geometry, flows, and graph-partitioning algorithms.
Commun. ACM 51(10): 96-105 (2008) |
| 88 | EE | Sagi 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 |
|---|
| 87 | EE | Srinath Sridhar,
Satish Rao,
Eran Halperin:
An Efficient and Accurate Graph-Based Approach to Detect Population Substructure.
RECOMB 2007: 503-517 |
| 86 | EE | Kamalika Chaudhuri,
Eran Halperin,
Satish Rao,
Shuheng Zhou:
A rigorous analysis of population stratification with limited data.
SODA 2007: 1046-1055 |
| 85 | EE | Baruch Awerbuch,
Rohit Khandekar,
Satish Rao:
Distributed algorithms for multicommodity flow problems via approximate steepest descent framework.
SODA 2007: 949-957 |
| 84 | EE | Jittat Fakcharoenphol,
Chris Harrelson,
Satish Rao:
The k-traveling repairmen problem.
ACM Transactions on Algorithms 3(4): (2007) |
| 83 | EE | Stavros 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 |
|---|
| 82 | EE | Kamalika Chaudhuri,
Satish Rao,
Samantha Riesenfeld,
Kunal Talwar:
A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.
ICALP (1) 2006: 191-201 |
| 81 | EE | Satish Rao,
Shuheng Zhou:
Edge Disjoint Paths in Moderately Connected Graphs.
ICALP (1) 2006: 202-213 |
| 80 | EE | Constantinos Daskalakis,
Cameron Hill,
Alexander Jaffe,
Radu Mihaescu,
Elchanan Mossel,
Satish Rao:
Maximal Accurate Forests from Distance Matrices.
RECOMB 2006: 281-295 |
| 79 | EE | Moses Charikar,
Mohammad Taghi Hajiaghayi,
Howard J. Karloff,
Satish Rao:
l22 spreading metrics for vertex ordering problems.
SODA 2006: 1018-1027 |
| 78 | EE | Kamalika Chaudhuri,
Kevin Chen,
Radu Mihaescu,
Satish Rao:
On the tandem duplication-random loss model of genome rearrangement.
SODA 2006: 564-570 |
| 77 | EE | Rohit Khandekar,
Satish Rao,
Umesh V. Vazirani:
Graph partitioning using single commodity flows.
STOC 2006: 385-390 |
| 76 | EE | Sagi Snir,
Satish Rao:
Using Max Cut to Enhance Rooted Trees Consistency.
IEEE/ACM Trans. Comput. Biology Bioinform. 3(4): 323-333 (2006) |
| 75 | EE | Jittat Fakcharoenphol,
Satish Rao:
Planar graphs, negative weight edges, shortest paths, and near linear time.
J. Comput. Syst. Sci. 72(5): 868-889 (2006) |
| 2005 |
|---|
| 74 | EE | Kamalika Chaudhuri,
Satish Rao,
Samantha Riesenfeld,
Kunal Talwar:
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs.
APPROX-RANDOM 2005: 26-39 |
| 73 | EE | Abraham 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 |
| 72 | EE | Shlomo Moran,
Satish Rao,
Sagi Snir:
Using Semi-definite Programming to Enhance Supertree Resolvability.
WABI 2005: 89-103 |
| 2004 |
|---|
| 71 | EE | Kevin Lang,
Satish Rao:
A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts.
IPCO 2004: 325-337 |
| 70 | EE | Kirsten Hildrum,
Sean Ma,
Satish Rao:
Brief announcement: randomized rumor spreading with fewer phone calls.
PODC 2004: 380 |
| 69 | EE | Kirsten Hildrum,
John Kubiatowicz,
Sean Ma,
Satish Rao:
A note on the nearest neighbor in growth-restricted metrics.
SODA 2004: 560-561 |
| 68 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning.
STOC 2004: 222-231 |
| 67 | EE | Jittat Fakcharoenphol,
Satish Rao,
Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics.
J. Comput. Syst. Sci. 69(3): 485-497 (2004) |
| 66 | EE | Satish Rao,
Andréa W. Richa:
New Approximation Techniques for Some Linear Ordering Problems.
SIAM J. Comput. 34(2): 388-404 (2004) |
| 65 | EE | Jittat Fakcharoenphol,
Satish Rao,
Kunal Talwar:
Approximating metrics by tree metrics.
SIGACT News 35(2): 60-70 (2004) |
| 2003 |
|---|
| 64 | EE | Kamalika Chaudhuri,
Brighten Godfrey,
Satish Rao,
Kunal Talwar:
Paths, Trees, and Minimum Latency Tours.
FOCS 2003: 36-45 |
| 63 | EE | Jittat Fakcharoenphol,
Chris Harrelson,
Satish Rao,
Kunal Talwar:
An improved approximation algorithm for the 0-extension problem.
SODA 2003: 257-265 |
| 62 | EE | Jittat Fakcharoenphol,
Chris Harrelson,
Satish Rao:
The k-traveling repairman problem.
SODA 2003: 655-664 |
| 61 | EE | Chris Harrelson,
Kirsten Hildrum,
Satish Rao:
A polynomial-time tree decomposition to minimize congestion.
SPAA 2003: 34-43 |
| 60 | EE | Jittat Fakcharoenphol,
Satish Rao,
Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics.
STOC 2003: 448-455 |
| 59 | EE | Eyal Amir,
Robert Krauthgamer,
Satish Rao:
Constant factor approximation of vertex-cuts in planar graphs.
STOC 2003: 90-99 |
| 2002 |
|---|
| 58 | EE | Kirsten 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 |
| 56 | EE | Frank 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 |
|---|
| 55 | EE | Mark W. Goudreau,
Stavros G. Kolliopoulos,
Satish Rao:
Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation.
INFOCOM 2000: 1624-1643 |
| 54 | EE | Guy 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 |
|---|
| 52 | EE | Stavros G. Kolliopoulos,
Satish Rao:
A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem.
ESA 1999: 378-389 |
| 51 | EE | Frank Thomson Leighton,
Satish Rao,
Aravind Srinivasan:
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.
SODA 1999: 643-652 |
| 50 | EE | Mark W. Goudreau,
Kevin Lang,
Girija J. Narlikar,
Satish Rao:
BOS is Boss: A Case for Bulk-Synchronous Object Systems.
SPAA 1999: 115-125 |
| 49 | EE | Satish 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) |
| 47 | EE | Frank 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) |
| 44 | EE | Andrew 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 |
| 42 | EE | Sanjeev Arora,
Prabhakar Raghavan,
Satish Rao:
Approximation Schemes for Euclidean k-Medians and Related Problems.
STOC 1998: 106-113 |
| 41 | EE | Satish Rao,
Warren D. Smith:
Approximating Geometrical Graphs via "Spanners" and "Banyans".
STOC 1998: 540-550 |
| 40 | EE | Andrew V. Goldberg,
Satish Rao:
Beyond the Flow Decomposition Barrier.
J. ACM 45(5): 783-797 (1998) |
| 39 | EE | Jonathan 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 |
|---|
| 38 | EE | Andrew V. Goldberg,
Satish Rao:
Beyond the Flow Decomposition Barrier.
FOCS 1997: 2-11 |
| 37 | EE | Andrew 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 |
| 34 | EE | Richard 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 |
| 25 | EE | Ingemar 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 |
| 22 | EE | Satish 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 |
| 19 | EE | Leslie Ann Goldberg,
Yossi Matias,
Satish Rao:
An Optical Simulation of Shared Memory.
SPAA 1994: 257-267 |
| 18 | EE | Philip 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 |
| 12 | EE | Leslie 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 |
| 11 | EE | Christos Kaklamanis,
Danny Krizanc,
Satish Rao:
New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies.
SPAA 1993: 325-334 |
| 10 | EE | William Aiello,
Baruch Awerbuch,
Bruce M. Maggs,
Satish Rao:
Approximate load balancing on dynamic and asynchronous networks.
STOC 1993: 632-641 |
| 9 | EE | Philip N. Klein,
Serge A. Plotkin,
Satish Rao:
Excluded minors, network decomposition, and multicommodity flow.
STOC 1993: 682-690 |
| 1992 |
|---|
| 8 | EE | Christos 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 |
