Satish B. Rao

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

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

Rao received his PhD from the Massachusetts Institute of Technology in 1989.^[3] The Mathematics Genealogy Project lists Frank Thomson Leighton as his doctoral advisor.^[6] 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.^[3]

At Berkeley, Rao is a professor in the Department of Electrical Engineering and Computer Sciences.^[1] Berkeley lists his research areas as biosystems and computational biology, and theory, and his research interests as combinatorial optimization and the design and analysis of algorithms.^[2] He is affiliated with the Simons Institute for the Theory of Computing and the Center for the Theoretical Foundations of Learning, Inference, Information, Intelligence, Mathematics and Microeconomics at Berkeley.^[1] His teaching at Berkeley has included discrete mathematics and probability theory, as well as graduate courses in combinatorial algorithms and data structures.^[2]

In 2026, Rao was listed by the California Secretary of State as a candidate for Governor of California in the June 2 statewide direct primary election, with Democratic Party preference and the ballot designation "Professor".^[7] His candidate statement appeared in the state's official voter information guide.^[8] The South Asian Times reported that Rao's campaign focused on education reform and administrative efficiency.^[9]

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.^[10] 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.^[11] In metric embeddings, Rao coauthored the Fakcharoenphol–Rao–Talwar paper giving a tight logarithmic bound for approximating finite metrics by tree metrics.^[12]

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 ${\displaystyle O(\log n)}$ to ${\displaystyle O({\sqrt {\log n}})}$.^[13][4] This work received the 2012 Fulkerson Prize.^[4]

Rao's publication record also includes work in computational biology, including graph-based approaches for detecting population substructure and methods related to phylogenetic tree estimation.^[14]

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".^[5] In 2012, he received the Fulkerson Prize with Arora and Vazirani for "Expander flows, geometric embeddings and graph partitioning".^[4]

• Leighton, Frank Thomson; Maggs, Bruce M.; Rao, Satish (1994). "Packet routing and job-shop scheduling in O(congestion + dilation) steps". Combinatorica. 14 (2): 167–186. doi:10.1007/BF01215349.
• Goldberg, Andrew V.; Rao, Satish (1998). "Beyond the flow decomposition barrier". Journal of the ACM. 45 (5): 783–797. doi:10.1145/290179.290181.
• Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM. 46 (6): 787–832. doi:10.1145/331524.331526.
• Even, Guy; Naor, Joseph; Rao, Satish; Schieber, Baruch (2000). "Divide-and-conquer approximation algorithms using spreading metrics". Journal of the ACM. 47 (4): 585–616. doi:10.1145/347476.347478.
• Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal (2003). "A tight bound on approximating arbitrary metrics by tree metrics". Proceedings of the 35th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 448–455. doi:10.1145/780542.780608.
• Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal (2004). "A tight bound on approximating arbitrary metrics by tree metrics". Journal of Computer and System Sciences. 69 (3): 485–497. doi:10.1016/j.jcss.2004.04.011.
• Rao, Satish (1999). "Small distortion and volume preserving embeddings for planar and Euclidean metrics". Proceedings of the Fifteenth Annual Symposium on Computational Geometry. Association for Computing Machinery. pp. 300–306. doi:10.1145/304893.304983.
• Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning". Journal of the ACM. 56 (2): 1–37. doi:10.1145/1502793.1502794.
• Biswal, Punyashloka; Lee, James R.; Rao, Satish (2010). "Eigenvalue bounds, spectral partitioning, and metrical deformations via flows". Journal of the ACM. 57 (3): 1–23. doi:10.1145/1706591.1706593.
• Le, Thien; Sy, Aaron; Molloy, Erin K.; Zhang, Qiuyi; Rao, Satish; Warnow, Tandy J. (2021). "Using Constrained-INC for large-scale gene tree and species tree estimation". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 18 (1): 2–15. doi:10.1109/TCBB.2019.2947041.
• Henzinger, Monika; Li, Jason; Rao, Satish; Wang, Di (2024). "Deterministic near-linear time minimum cut in weighted graphs". Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 3089–3139.

• Satish B. Rao publications indexed by Google Scholar
• Satish Rao's homepage
• Satish Rao publications at DBLP