Satish Rao

According to our database, Satish Rao authored at least 115 papers between 1987 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.

Monika Henzinger, Jason Li, Satish Rao, Di Wang

CoRR, 2024

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.

Monika Henzinger, Jason Li, Satish Rao, Di Wang

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2021

Using Constrained-INC for Large-Scale Gene Tree and Species Tree Estimation.

Thien Le, Aaron Sy, Erin K. Molloy, Qiuyi Zhang, Satish Rao, Tandy J. Warnow

IEEE ACM Trans. Comput. Biol. Bioinform., 2021

2020

Local Flow Partitioning for Faster Edge Connectivity.

Monika Henzinger, Satish Rao, Di Wang

SIAM J. Comput., 2020

2019

Constrained incremental tree building: new absolute fast converging phylogeny estimation methods with improved scalability and accuracy.

Qiuyi Zhang, Satish Rao, Tandy J. Warnow

Algorithms Mol. Biol., 2019

Using INC Within Divide-and-Conquer Phylogeny Estimation.

Thien Le, Aaron Sy, Erin K. Molloy, Qiuyi (Richard) Zhang, Satish Rao, Tandy J. Warnow

Proceedings of the Algorithms for Computational Biology - 6th International Conference, 2019

2018

New Absolute Fast Converging Phylogeny Estimation Methods with Improved Scalability and Accuracy.

Qiuyi (Richard) Zhang, Satish Rao, Tandy J. Warnow

Proceedings of the 18th International Workshop on Algorithms in Bioinformatics, 2018

Localization of Electrical Flows.

Aaron Schild, Satish Rao, Nikhil Srivastava

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Strongly refuting random CSPs below the spectral threshold.

Prasad Raghavendra, Satish Rao, Tselil Schramm

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Capacity Releasing Diffusion for Speed and Locality.

Di Wang, Kimon Fountoulakis, Monika Henzinger, Michael W. Mahoney, Satish Rao

Proceedings of the 34th International Conference on Machine Learning, 2017

2016

Approximating Metric Spaces by Tree Metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

Encyclopedia of Algorithms, 2016

Shortest Paths in Planar Graphs with Negative Weight Edges.

Jittat Fakcharoenphol, Satish Rao

Encyclopedia of Algorithms, 2016

BIGMAC : breaking inaccurate genomes and merging assembled contigs for long read metagenomic assembly.

Ka-Kit Lam, Richard Hall, Alicia Clum, Satish Rao

BMC Bioinform., 2016

Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction.

Di Wang, Satish Rao, Michael W. Mahoney

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time.

Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent.

Di Wang, Michael W. Mahoney, Nishanth Mohan, Satish Rao

CoRR, 2015

2013

Fast Phylogeny Reconstruction Through Learning of Ancestral Sequences.

Radu Mihaescu, Cameron Hill, Satish Rao

Algorithmica, 2013

A new approach to computing maximum flows using electrical flows.

Yin Tat Lee, Satish Rao, Nikhil Srivastava

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Distributed algorithms for multicommodity flow problems via approximate steepest descent framework.

Baruch Awerbuch, Rohit Khandekar, Satish Rao

ACM Trans. Algorithms, 2012

Query Strategies for Evading Convex-Inducing Classifiers.

Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven J. Lee, Satish Rao, J. D. Tygar

J. Mach. Learn. Res., 2012

2010

Quartets MaxCut: A Divide and Conquer Quartets Algorithm.

Sagi Snir, Satish Rao

IEEE ACM Trans. Comput. Biol. Bioinform., 2010

Edge Disjoint Paths in Moderately Connected Graphs.

Satish Rao, Shuheng Zhou

SIAM J. Comput., 2010

Near-Optimal Evasion of Convex-Inducing Classifiers.

Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Steven J. Lee, Satish Rao, Anthony Tran, J. Doug Tygar

Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010

Eigenvalue bounds, spectral partitioning, and metrical deformations via flows.

Punyashloka Biswal, James R. Lee, Satish Rao

J. ACM, 2010

<i><i>l</i></i>₂² Spreading Metrics for Vertex Ordering Problems.

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao

Algorithmica, 2010

2009

A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids.

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

Theor. Comput. Sci., 2009

Stealthy poisoning attacks on PCA-based anomaly detectors.

Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, J. D. Tygar

SIGMETRICS Perform. Evaluation Rev., 2009

Graph partitioning using single commodity flows.

Rohit Khandekar, Satish Rao, Umesh V. Vazirani

J. ACM, 2009

Expander flows, geometric embeddings and graph partitioning.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

J. ACM, 2009

What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs.

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

Algorithmica, 2009

ANTIDOTE: understanding and defending against poisoning of anomaly detectors.

Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, J. D. Tygar

Proceedings of the 9th ACM SIGCOMM Internet Measurement Conference, IMC 2009, Chicago, 2009

2008

Approximating Metric Spaces by Tree Metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Shortest Paths in Planar Graphs with Negative Weight Edges.

Jittat Fakcharoenphol, Satish Rao

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Short Quartet Puzzling: A New Quartet-Based Phylogeny Reconstruction Algorithm.

Sagi Snir, Tandy J. Warnow, Satish Rao

J. Comput. Biol., 2008

Geometry, flows, and graph-partitioning algorithms.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

Commun. ACM, 2008

Beyond Gaussians: Spectral Methods for Learning Mixtures of Heavy-Tailed Distributions.

Kamalika Chaudhuri, Satish Rao

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Learning Mixtures of Product Distributions Using Correlations and Independence.

Kamalika Chaudhuri, Satish Rao

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

The <i>k</i>-traveling repairmen problem.

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao

ACM Trans. Algorithms, 2007

A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem.

Stavros G. Kolliopoulos, Satish Rao

SIAM J. Comput., 2007

A rigorous analysis of population stratification with limited data.

Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

An Efficient and Accurate Graph-Based Approach to Detect Population Substructure.

Srinath Sridhar, Satish Rao, Eran Halperin

Proceedings of the Research in Computational Molecular Biology, 2007

2006

Using Max Cut to Enhance Rooted Trees Consistency.

Sagi Snir, Satish Rao

IEEE ACM Trans. Comput. Biol. Bioinform., 2006

Planar graphs, negative weight edges, shortest paths, and near linear time.

Jittat Fakcharoenphol, Satish Rao

J. Comput. Syst. Sci., 2006

On the tandem duplication-random loss model of genome rearrangement.

Kamalika Chaudhuri, Kevin C. Chen, Radu Mihaescu, Satish Rao

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

<i>l</i>²₂ spreading metrics for vertex ordering problems.

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Maximal Accurate Forests from Distance Matrices.

Constantinos Daskalakis, Cameron Hill, Alexander Jaffe, Radu Mihaescu, Elchanan Mossel, Satish Rao

Proceedings of the Research in Computational Molecular Biology, 2006

A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Using Semi-definite Programming to Enhance Supertree Resolvability.

Shlomo Moran, Satish Rao, Sagi Snir

Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

Lower Bounds for Maximum Parsimony with Gene Order Data.

Abraham Bachrach, Kevin C. Chen, Chris Harrelson, Radu Mihaescu, Satish Rao, Apurva Shah

Proceedings of the Comparative Genomics, 2005

2004

Approximating metrics by tree metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

SIGACT News, 2004

New Approximation Techniques for Some Linear Ordering Problems.

Satish Rao, Andréa W. Richa

SIAM J. Comput., 2004

Distributed Object Location in a Dynamic Network.

Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao

Theory Comput. Syst., 2004

A tight bound on approximating arbitrary metrics by tree metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

J. Comput. Syst. Sci., 2004

A note on the nearest neighbor in growth-restricted metrics.

Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Brief announcement: randomized rumor spreading with fewer phone calls.

Kirsten Hildrum, Sean Ma, Satish Rao

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts.

Kevin J. Lang, Satish Rao

Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003

Constant factor approximation of vertex-cuts in planar graphs.

Eyal Amir, Robert Krauthgamer, Satish Rao

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A polynomial-time tree decomposition to minimize congestion.

Chris Harrelson, Kirsten Hildrum, Satish Rao

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

An improved approximation algorithm for the 0-extension problem.

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

The k-traveling repairman problem.

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Paths, Trees, and Minimum Latency Tours.

Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.

Frank Thomson Leighton, Chi-Jen Lu, Satish Rao, Aravind Srinivasan

SIAM J. Comput., 2001

Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time.

Jittat Fakcharoenphol, Satish Rao

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Computing Vertex Connectivity: New Bounds from Old Techniques.

Monika Rauch Henzinger, Satish Rao, Harold N. Gabow

J. Algorithms, 2000

Divide-and-conquer approximation algorithms via spreading metrics.

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

J. ACM, 2000

Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation.

Mark W. Goudreau, Stavros G. Kolliopoulos, Satish Rao

Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

1999

Portable and Efficient Parallel Computing Using the BSP Model.

Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas

IEEE Trans. Computers, 1999

Flows in Undirected Unit Capacity Networks.

Andrew V. Goldberg, Satish Rao

SIAM J. Discret. Math., 1999

An Optical Simulation of Shared Memory.

Leslie Ann Goldberg, Yossi Matias, Satish Rao

SIAM J. Comput., 1999

Fast Approximate Graph Partitioning Algorithms.

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

SIAM J. Comput., 1999

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.

Frank Thomson Leighton, Satish Rao

J. ACM, 1999

BOS is Boss: A Case for Bulk-Synchronous Object Systems.

Mark W. Goudreau, Kevin J. Lang, Girija J. Narlikar, Satish Rao

Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.

Frank Thomson Leighton, Satish Rao, Aravind Srinivasan

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem.

Stavros G. Kolliopoulos, Satish Rao

Proceedings of the Algorithms, 1999

Small Distortion and Volume Preserving Embeddings for Planar and Euclidean Metrics.

Satish Rao

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

BSPlib: The BSP programming library.

Jonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas, Rob H. Bisseling

Parallel Comput., 1998

Beyond the Flow Decomposition Barrier.

Andrew V. Goldberg, Satish Rao

J. ACM, 1998

Approximating Geometrical Graphs via "Spanners" and "Banyans".

Satish Rao, Warren D. Smith

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximation Schemes for Euclidean <i>k</i>-Medians and Related Problems.

Sanjeev Arora, Prabhakar Raghavan, Satish Rao

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

New Approximation Techniques for Some Ordering Problems.

Satish Rao, Andréa W. Richa

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Multicommodity Flow and Circuit Switching.

Tom Leighton, Satish Rao, Aravind Srinivasan

Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences, 1998

1997

A Multimedia Presentation Toolkit for the World Wide Web.

Johnny Wong, Satish Rao, Naveen Ramaiah

Softw. Pract. Exp., 1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.

Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao

SIAM J. Comput., 1997

New Graph Decompositions with Applications to Emulations.

Christos Kaklamanis, Danny Krizanc, Satish Rao

Theory Comput. Syst., 1997

Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers.

Charles E. Leiserson, Satish Rao, Sivan Toledo

J. Comput. Syst. Sci., 1997

Faster Shortest-Path Algorithms for Planar Graphs.

Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian

J. Comput. Syst. Sci., 1997

Approximation Algorithms for Steiner and Directed Multicuts.

Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos

J. Algorithms, 1997

Work-preserving emulations of fixed-connection networks.

Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg, Eric J. Schwabe

J. ACM, 1997

Spreading Metric Based Graph Partitioning Algorithms.

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, 1997

1996

A Maximum Likelihood Stereo Algorithm.

Ingemar J. Cox, Sunita L. Hingorani, Satish Rao, Bruce M. Maggs

Comput. Vis. Image Underst., 1996

Towards Efficiency and Portability: Programming with the BSP Model.

Mark W. Goudreau, Kevin J. Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas

Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

"Ratio regions": a technique for image segmentation.

Ingemar J. Cox, Satish Rao, Yu Zhong

Proceedings of the 13th International Conference on Pattern Recognition, 1996

1995

An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications.

Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi

Comb., 1995

Efficient communication using total-exchange.

Satish Rao, Torsten Suel, Thanasis Tsantilas, Mark W. Goudreau

Proceedings of IPPS '95, 1995

Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings.

Milena Mihail, Christos Kaklamanis, Satish Rao

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract).

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Randomized Routing and Sorting on Fixed-Connection Networks.

Frank Thomson Leighton, Bruce M. Maggs, Abhiram G. Ranade, Satish Rao

J. Algorithms, 1994

Packet Routing and Job-Shop Scheduling in <i>O</i>(Congestion + Dilation) Steps.

Frank Thomson Leighton, Bruce M. Maggs, Satish Rao

Comb., 1994

Shallow Excluded Minors and Improved Graph Decompositions.

Serge A. Plotkin, Satish Rao, Warren D. Smith

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Excluded minors, network decomposition, and multicommodity flow.

Philip N. Klein, Serge A. Plotkin, Satish Rao

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Approximate load balancing on dynamic and asynchronous networks.

William Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies.

Christos Kaklamanis, Danny Krizanc, Satish Rao

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.

Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Finding Near-Optimal Cuts: An Empirical Evaluation.

Kevin J. Lang, Satish Rao

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract)

Charles E. Leiserson, Satish Rao, Sivan Toledo

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Universal Emulations with Sublogarithmic Slowdown

Christos Kaklamanis, Danny Krizanc, Satish Rao

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract)

Satish Rao

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Simple Path Selection for Optimal Routing on Processor Arrays.

Christos Kaklamanis, Danny Krizanc, Satish Rao

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Stereo Without Disparity Gradient Smoothing: A Bayesian Sensor Fusion Solution.

Ingemar J. Cox, Sunita L. Hingorani, Bruce M. Maggs, Satish Rao

Proceedings of the British Machine Vision Conference, 1992

1990

Approximation through Multicommodity Flow

Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)

Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract)

Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms

Frank Thomson Leighton, Satish Rao

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Universal Packet Routing Algorithms (Extended Abstract)

Frank Thomson Leighton, Bruce M. Maggs, Satish Rao

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Finding Near Optimal Separators in Planar Graphs

Satish Rao

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987