# Satish Rao

According to our database

Collaborative distances:

^{1}, Satish Rao authored at least 112 papers between 1987 and 2019.Collaborative distances:

## Awards

## ACM Fellow

ACM Fellow 2013, "For contributions to algorithms for graph partitioning and for single- and multi-commodity flows.".

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

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

Algorithms for Molecular Biology, 2019

Using INC Within Divide-and-Conquer Phylogeny Estimation.

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

2018

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

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

Localization of Electrical Flows.

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

2017

Strongly refuting random CSPs below the spectral threshold.

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

Local Flow Partitioning for Faster Edge Connectivity.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Capacity Releasing Diffusion for Speed and Locality.

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

2016

Approximating Metric Spaces by Tree Metrics.

Encyclopedia of Algorithms, 2016

Shortest Paths in Planar Graphs with Negative Weight Edges.

Encyclopedia of Algorithms, 2016

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

BMC Bioinformatics, 2016

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

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.

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

2013

Fast Phylogeny Reconstruction Through Learning of Ancestral Sequences.

Algorithmica, 2013

A new approach to computing maximum flows using electrical flows.

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Query Strategies for Evading Convex-Inducing Classifiers.

J. Mach. Learn. Res., 2012

2010

Quartets MaxCut: A Divide and Conquer Quartets Algorithm.

IEEE/ACM Trans. Comput. Biology Bioinform., 2010

Near-Optimal Evasion of Convex-Inducing Classifiers.

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

Algorithmica, 2010

2009

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

Theor. Comput. Sci., 2009

Stealthy poisoning attacks on PCA-based anomaly detectors.

SIGMETRICS Performance Evaluation Review, 2009

ANTIDOTE: understanding and defending against poisoning of anomaly detectors.

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

2008

Approximating Metric Spaces by Tree Metrics.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Shortest Paths in Planar Graphs with Negative Weight Edges.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

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

Journal of Computational Biology, 2008

Geometry, flows, and graph-partitioning algorithms.

Commun. ACM, 2008

Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

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

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

Learning Mixtures of Product Distributions Using Correlations and Independence.

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

2007

The

*k*-traveling repairmen problem.
ACM Trans. Algorithms, 2007

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

SIAM J. Comput., 2007

A rigorous analysis of population stratification with limited data.

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

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

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

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

Proceedings of the Research in Computational Molecular Biology, 2007

2006

Using Max Cut to Enhance Rooted Trees Consistency.

IEEE/ACM Trans. Comput. Biology Bioinform., 2006

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

J. Comput. Syst. Sci., 2006

Graph partitioning using single commodity flows.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

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

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

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

Maximal Accurate Forests from Distance Matrices.

Proceedings of the Research in Computational Molecular Biology, 2006

Edge Disjoint Paths in Moderately Connected Graphs.

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

A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.

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

2005

Using Semi-definite Programming to Enhance Supertree Resolvability.

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

Lower Bounds for Maximum Parsimony with Gene Order Data.

Proceedings of the Comparative Genomics, 2005

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

Proceedings of the Approximation, 2005

2004

Approximating metrics by tree metrics.

SIGACT News, 2004

New Approximation Techniques for Some Linear Ordering Problems.

SIAM J. Comput., 2004

Expander flows, geometric embeddings and graph partitioning.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

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

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

Brief announcement: randomized rumor spreading with fewer phone calls.

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.

Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003

A tight bound on approximating arbitrary metrics by tree metrics.

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

Constant factor approximation of vertex-cuts in planar graphs.

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

A polynomial-time tree decomposition to minimize congestion.

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.

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

The k-traveling repairman problem.

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

Paths, Trees, and Minimum Latency Tours.

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

2002

Distributed object location in a dynamic network.

Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2002

2001

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

SIAM J. Comput., 2001

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

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

2000

Divide-and-conquer approximation algorithms via spreading metrics.

J. ACM, 2000

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

Proceedings of the Proceedings IEEE INFOCOM 2000, 2000

1999

Portable and Efficient Parallel Computing Using the BSP Model.

IEEE Trans. Computers, 1999

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

J. ACM, 1999

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

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.

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

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

Proceedings of the Algorithms, 1999

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

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

BSPlib: The BSP programming library.

Parallel Computing, 1998

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

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

Approximation Schemes for Euclidean

*k*-Medians and Related Problems.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

New Approximation Techniques for Some Ordering Problems.

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

Multicommodity Flow and Circuit Switching.

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

1997

A Multimedia Presentation Toolkit for the World Wide Web.

Softw., Pract. Exper., 1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.

SIAM J. Comput., 1997

New Graph Decompositions with Applications to Emulations.

Theory Comput. Syst., 1997

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

J. Comput. Syst. Sci., 1997

Faster Shortest-Path Algorithms for Planar Graphs.

J. Comput. Syst. Sci., 1997

Approximation Algorithms for Steiner and Directed Multicuts.

J. Algorithms, 1997

Work-preserving emulations of fixed-connection networks.

J. ACM, 1997

Fast Approximate Graph Partitioning Algorithms.

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Spreading Metric Based Graph Partitioning Algorithms.

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

Flows in Undirected Unit Capacity Networks.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Beyond the Flow Decomposition Barrier.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

A Maximum Likelihood Stereo Algorithm.

Computer Vision and Image Understanding, 1996

Towards Efficiency and Portability: Programming with the BSP Model.

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

"Ratio regions": a technique for image segmentation.

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

Computing Vertex Connectivity: New Bounds from Old Techniques.

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

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

Combinatorica, 1995

Efficient communication using total-exchange.

Proceedings of IPPS '95, 1995

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

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

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

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

1994

Randomized Routing and Sorting on Fixed-Connection Networks.

J. Algorithms, 1994

Packet Routing and Job-Shop Scheduling in

*O*(Congestion + Dilation) Steps.
Combinatorica, 1994

Faster shortest-path algorithms for planar graphs.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

An Optical Simulation of Shared Memory.

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Shallow Excluded Minors and Improved Graph Decompositions.

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

1993

Excluded minors, network decomposition, and multicommodity flow.

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

Approximate load balancing on dynamic and asynchronous networks.

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

New Graph Decompositions and Fast Emulations in Hypercubes and Butterflies.

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.

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

Finding Near-Optimal Cuts: An Empirical Evaluation.

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)

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

Universal Emulations with Sublogarithmic Slowdown

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)

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

Simple Path Selection for Optimal Routing on Processor Arrays.

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

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

Proceedings of the British Machine Vision Conference, 1992

1990

Approximation through Multicommodity Flow

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

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

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

1989

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

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

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

Universal Packet Routing Algorithms (Extended Abstract)

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

1987

Finding Near Optimal Separators in Planar Graphs

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