Satish B. Rao

Satish B. Rao
Satish B. Rao
Alma mater	Frank Thomson Leighton

Satish B. Rao is an American computer scientist who is a professor of computer science at the University of California, Berkeley.^[1]^[2]

Biography

Satish Rao received his PhD from the Massachusetts Institute of Technology in 1989 and joined the faculty at the University of California, Berkeley in 1999.^[3]

Research and awards

Rao's research focuses on

graph partitioning, and single- and multi-commodity flows (maximum flow problem).^[4]

Rao is an

approximation ratio for graph separators

and related problems from

O(\log n)

to

O({\sqrt {\log n}})

.[6]^[7] Rao teaches discrete mathematics and probability theory at the University of California, Berkeley.^[1]

Publications

Satish Rao has published over 100 publications and is cited frequently.^[8]

Selected publications

S. Arora, S. Rao, and U. Vazirani. "Expander flows, geometric embeddings and graph partitioning," Journal of the ACM (JACM) 56.2 (2009): 1-37.
J. Fakcharoenphol, S. Rao, and K. Talwar, "A tight bound on approximating arbitrary metrics by tree metrics," in Proceedings of 35th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 2003, pp. 448–455.
K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed object location in a dynamic network," in Proceedings of 14th Annual ACM Symp. on Parallel Algorithms and Architectures, New York, NY: ACM Press, 2002, pp. 41–52.
G. Even, J. S. Naor, S. Rao, and B. Schieber, "Divide-and-conquer approximation algorithms using spreading metrics," Journal of the ACM, vol. 47, no. 4, pp. 585–616, July 2000.
T. Leighton and S. Rao, "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms," Journal of the ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
S. Rao, "Small distortion and volume preserving embeddings for planar and Euclidean metrics," in Proceedings of 15th Annual Symp. on Computational Geometry, New York, NY: ACM Press, 1999, pp. 300–306.
A. V. Goldberg and S. Rao, "Beyond the flow decomposition barrier," Journal of the ACM, vol. 45, no. 5, pp. 783–797, Sep. 1998.
J. Ingemar Cox, S. L. Hingorani, S. Rao and B. M. Maggs. "A maximum likelihood stereo algorithm," Computer vision and image understanding 63, no. 3 (1996): 542-567.
F. T. Leighton, B. M. Maggs, and S. Rao, "Packet routing and job-shop scheduling in O(congestion + dilation) steps," Combinatorica, vol. 14, no. 2, pp. 167–186, June 1994.