Satish Rao

Radu Mihaescu, Cameron Hill, Satish Rao: Fast Phylogeny Reconstruction Through Learning of Ancestral Sequences. Algorithmica 66(2): 419-449 (2013)

Baruch Awerbuch, Rohit Khandekar, Satish Rao: Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. ACM Transactions on Algorithms 9(1): 3 (2012)

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao: l₂² Spreading Metrics for Vertex Ordering Problems. Algorithmica 56(4): 577-604 (2010)

Punyashloka Biswal, James R. Lee, Satish Rao: Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM 57(3) (2010)

Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Steven J. Lee, Satish Rao, Anthony Tran, J. Doug Tygar: Near-Optimal Evasion of Convex-Inducing Classifiers. Journal of Machine Learning Research - Proceedings Track 9: 549-556 (2010)

Satish Rao, Shuheng Zhou: Edge Disjoint Paths in Moderately Connected Graphs. SIAM J. Comput. 39(5): 1856-1887 (2010)

Sagi Snir, Satish Rao: Quartets MaxCut: A Divide and Conquer Quartets Algorithm. IEEE/ACM Trans. Comput. Biology Bioinform. 7(4): 704-718 (2010)

Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Steven J. Lee, Satish Rao, Anthony Tran, J. D. Tygar: Near-Optimal Evasion of Convex-Inducing Classifiers. CoRR abs/1003.2751 (2010)

Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven J. Lee, Satish Rao, J. D. Tygar: Query Strategies for Evading Convex-Inducing Classifiers. CoRR abs/1007.0484 (2010)

Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. Algorithmica 55(1): 157-189 (2009)

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)

Rohit Khandekar, Satish Rao, Umesh V. Vazirani: Graph partitioning using single commodity flows. J. ACM 56(4) (2009)

Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, J. D. Tygar: Stealthy poisoning attacks on PCA-based anomaly detectors. SIGMETRICS Performance Evaluation Review 37(2): 73-74 (2009)

Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. Theor. Comput. Sci. 410(44): 4489-4503 (2009)

Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, J. D. Tygar: ANTIDOTE: understanding and defending against poisoning of anomaly detectors. Internet Measurement Conference 2009: 1-14

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)

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)

Kamalika Chaudhuri, Satish Rao: Learning Mixtures of Product Distributions Using Correlations and Independence. COLT 2008: 9-20

Kamalika Chaudhuri, Satish Rao: Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions. COLT 2008: 21-32

Punyashloka Biswal, James R. Lee, Satish Rao: Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. FOCS 2008: 751-760

Jittat Fakcharoenphol, Satish Rao: Shortest Paths in Planar Graphs with Negative Weight Edges. Encyclopedia of Algorithms 2008

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: Approximating Metric Spaces by Tree Metrics. Encyclopedia of Algorithms 2008

Punyashloka Biswal, James R. Lee, Satish Rao: Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. CoRR abs/0808.0148 (2008)

Radu Mihaescu, Cameron Hill, Satish Rao: Fast phylogeny reconstruction through learning of ancestral sequences. CoRR abs/0812.1587 (2008)

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)

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao: The k-traveling repairmen problem. ACM Transactions on Algorithms 3(4) (2007)

Srinath Sridhar, Satish Rao, Eran Halperin: An Efficient and Accurate Graph-Based Approach to Detect Population Substructure. RECOMB 2007: 503-517

Baruch Awerbuch, Rohit Khandekar, Satish Rao: Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. SODA 2007: 949-957

Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou: A rigorous analysis of population stratification with limited data. SODA 2007: 1046-1055

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

Sagi Snir, Satish Rao: Using Max Cut to Enhance Rooted Trees Consistency. IEEE/ACM Trans. Comput. Biology Bioinform. 3(4): 323-333 (2006)

Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar: A Push-Relabel Algorithm for Approximating Degree Bounded MSTs. ICALP (1) 2006: 191-201

Satish Rao, Shuheng Zhou: Edge Disjoint Paths in Moderately Connected Graphs. ICALP (1) 2006: 202-213

Constantinos Daskalakis, Cameron Hill, Alexander Jaffe, Radu Mihaescu, Elchanan Mossel, Satish Rao: Maximal Accurate Forests from Distance Matrices. RECOMB 2006: 281-295

Kamalika Chaudhuri, Kevin Chen, Radu Mihaescu, Satish Rao: On the tandem duplication-random loss model of genome rearrangement. SODA 2006: 564-570

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao: l²₂ spreading metrics for vertex ordering problems. SODA 2006: 1018-1027

Rohit Khandekar, Satish Rao, Umesh V. Vazirani: Graph partitioning using single commodity flows. STOC 2006: 385-390

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

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

Shlomo Moran, Satish Rao, Sagi Snir: Using Semi-definite Programming to Enhance Supertree Resolvability. WABI 2005: 89-103

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)

Satish Rao, Andréa W. Richa: New Approximation Techniques for Some Linear Ordering Problems. SIAM J. Comput. 34(2): 388-404 (2004)

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: Approximating metrics by tree metrics. SIGACT News 35(2): 60-70 (2004)

Kevin J. Lang, Satish Rao: A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts. IPCO 2004: 325-337

Kirsten Hildrum, Sean Ma, Satish Rao: Brief announcement: randomized rumor spreading with fewer phone calls. PODC 2004: 380

Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao: A note on the nearest neighbor in growth-restricted metrics. SODA 2004: 560-561

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231

Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar: Paths, Trees, and Minimum Latency Tours. FOCS 2003: 36-45

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar: An improved approximation algorithm for the 0-extension problem. SODA 2003: 257-265

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao: The k-traveling repairman problem. SODA 2003: 655-664

Chris Harrelson, Kirsten Hildrum, Satish Rao: A polynomial-time tree decomposition to minimize congestion. SPAA 2003: 34-43

Eyal Amir, Robert Krauthgamer, Satish Rao: Constant factor approximation of vertex-cuts in planar graphs. STOC 2003: 90-99

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003: 448-455

Kirsten Hildrum, John Kubiatowicz, Satish Rao, Ben Y. Zhao: Distributed object location in a dynamic network. SPAA 2002: 41-52

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)

Jittat Fakcharoenphol, Satish Rao: Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. FOCS 2001: 232-241

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4): 585-616 (2000)

Monika Rauch Henzinger, Satish Rao, Harold N. Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques. J. Algorithms 34(2): 222-250 (2000)

Mark W. Goudreau, Stavros G. Kolliopoulos, Satish Rao: Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation. INFOCOM 2000: 1624-1643

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)

Leslie Ann Goldberg, Yossi Matias, Satish Rao: An Optical Simulation of Shared Memory. SIAM J. Comput. 28(5): 1829-1847 (1999)

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6): 2187-2214 (1999)

Andrew V. Goldberg, Satish Rao: Flows in Undirected Unit Capacity Networks. SIAM J. Discrete Math. 12(1): 1-5 (1999)

Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas: Portable and Efficient Parallel Computing Using the BSP Model. IEEE Trans. Computers 48(7): 670-689 (1999)

Satish Rao: Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics. Symposium on Computational Geometry 1999: 300-306

Stavros G. Kolliopoulos, Satish Rao: A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem. ESA 1999: 378-389

Frank Thomson Leighton, Satish Rao, Aravind Srinivasan: New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning. SODA 1999: 643-652

Mark W. Goudreau, Kevin J. Lang, Girija J. Narlikar, Satish Rao: BOS is Boss: A Case for Bulk-Synchronous Object Systems. SPAA 1999: 115-125

Andrew V. Goldberg, Satish Rao: Beyond the Flow Decomposition Barrier. J. ACM 45(5): 783-797 (1998)

Jonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas, Rob H. Bisseling: BSPlib: The BSP programming library. Parallel Computing 24(14): 1947-1980 (1998)

Satish Rao, Andréa W. Richa: New Approximation Techniques for Some Ordering Problems. SODA 1998: 211-218

Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation Schemes for Euclidean k-Medians and Related Problems. STOC 1998: 106-113

Satish Rao, Warren D. Smith: Approximating Geometrical Graphs via "Spanners" and "Banyans". STOC 1998: 540-550

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)

Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos: Approximation Algorithms for Steiner and Directed Multicuts. J. Algorithms 22(2): 241-269 (1997)

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)

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)

Christos Kaklamanis, Danny Krizanc, Satish Rao: New Graph Decompositions with Applications to Emulations. Theory Comput. Syst. 30(1): 39-49 (1997)

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)

Johnny Wong, Satish Rao, Naveen Ramaiah: A Multimedia Presentation Toolkit for the World Wide Web. Softw., Pract. Exper. 27(4): 425-446 (1997)

Andrew V. Goldberg, Satish Rao: Beyond the Flow Decomposition Barrier. FOCS 1997: 2-11

Andrew V. Goldberg, Satish Rao: Flows in Undirected Unit Capacity Networks. FOCS 1997: 32-34

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Spreading Metric Based Graph Partitioning Algorithms. PPSC 1997

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. SODA 1997: 639-648

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)

Monika Rauch Henzinger, Satish Rao, Harold N. Gabow: Computing Vertex Connectivity: New Bounds from Old Techniques. FOCS 1996: 462-471

Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas: Towards Efficiency and Portability: Programming with the BSP Model. SPAA 1996: 1-12

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)

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). FOCS 1995: 62-71

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

Satish Rao, Torsten Suel, Thanasis Tsantilas, Mark W. Goudreau: Efficient communication using total-exchange. IPPS 1995: 544-550

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)

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)

Serge A. Plotkin, Satish Rao, Warren D. Smith: Shallow Excluded Minors and Improved Graph Decompositions. SODA 1994: 462-470

Leslie Ann Goldberg, Yossi Matias, Satish Rao: An Optical Simulation of Shared Memory. SPAA 1994: 257-267

Philip N. Klein, Satish Rao, Monika Rauch Henzinger, Sairam Subramanian: Faster shortest-path algorithms for planar graphs. STOC 1994: 27-37

Christos Kaklamanis, Danny Krizanc, Satish Rao: Universal Emulations with Sublogarithmic Slowdown. FOCS 1993: 341-350

Charles E. Leiserson, Satish Rao, Sivan Toledo: Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract). FOCS 1993: 704-713

Kevin J. Lang, Satish Rao: Finding Near-Optimal Cuts: An Empirical Evaluation. SODA 1993: 212-221

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

Christos Kaklamanis, Danny Krizanc, Satish Rao: New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies. SPAA 1993: 325-334

William Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao: Approximate load balancing on dynamic and asynchronous networks. STOC 1993: 632-641

Philip N. Klein, Serge A. Plotkin, Satish Rao: Excluded minors, network decomposition, and multicommodity flow. STOC 1993: 682-690

Ingemar J. Cox, Sunita L. Hingorani, Bruce M. Maggs, Satish Rao: Stereo Without Disparity Gradient Smoothing: A Bayesian Sensor Fusion Solution. BMVC 1992: 1-10

Christos Kaklamanis, Danny Krizanc, Satish Rao: Simple Path Selection for Optimal Routing on Processor Arrays. SPAA 1992: 23-30

Satish Rao: Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract). STOC 1992: 229-240

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

Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao: Approximation through Multicommodity Flow. FOCS 1990: 726-737

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

Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Universal Packet Routing Algorithms (Extended Abstract). FOCS 1988: 256-269

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

Satish Rao: Finding Near Optimal Separators in Planar Graphs. FOCS 1987: 225-237