Satish B. Rao

Satish B. Rao is an American computer scientist and professor of computer science at the University of California, Berkeley. His research is in the design and analysis of algorithms, with work in combinatorial optimization, graph partitioning, network flow, metric embeddings, and computational biology.

Rao received the Fulkerson Prize in 2012 with Sanjeev Arora and Umesh Vazirani for their work on approximation algorithms for the sparsest cut problem. He was named an ACM Fellow in 2013 for contributions to algorithms for graph partitioning and for single- and multi-commodity flows.

Biography Rao received his PhD from the Massachusetts Institute of Technology in 1989. After completing his doctorate, Rao held a scientist position at NEC Laboratories until 1999, when he joined the faculty of the University of California, Berkeley. His candidate statement appeared in the state's official voter information guide. The South Asian Times reported that Rao's campaign focused on education reform and administrative efficiency. However he ultimately secured just 0.06% of the votes and was eliminated in the primary.

Research Rao's research has focused on approximation algorithms and optimization problems involving graphs, cuts, flows, and embeddings. With Leighton, he developed multicommodity max-flow min-cut theorems and applied them to approximation algorithms for graph partitioning and other NP-hard optimization problems. The paper was part of a line of work connecting network flows, separators, and approximation guarantees for difficult graph problems.

Rao has also worked on maximum-flow algorithms. With Andrew V. Goldberg, he coauthored "Beyond the Flow Decomposition Barrier", which introduced a maximum-flow approach based on residual capacities and length functions. In metric embeddings, Rao coauthored the Fakcharoenphol–Rao–Talwar paper giving a tight logarithmic bound for approximating finite metrics by tree metrics.

With Arora and Vazirani, Rao developed the expander-flow method for graph partitioning. Their Journal of the ACM paper, "Expander flows, geometric embeddings and graph partitioning", improved the approximation ratio for graph separators and related problems from to .

Awards and honors Rao was named a Fellow of the Association for Computing Machinery in 2013 for "contributions to algorithms for graph partitioning and for single- and multi-commodity flows". In 2012, he received the Fulkerson Prize with Arora and Vazirani for "Expander flows, geometric embeddings and graph partitioning".

Selected publications