# Faculty Publications - Satish Rao

## Book chapters or sections

- J. Fakcharoenphol and S. Rao, "Shortest Paths in Planar Graphs with Negative Weight Edges," in
*Encyclopedia of Algorithms*, M. Y. Kao, Ed., Springer Reference, Secaucus, NJ: Springer US, 2008. - J. Fakcharoenphol, S. Rao, and K. Talwar, "Approximating Metric Space by Tree Metrics," in
*Encyclopedia of Algorithms*, M. Y. Kao, Ed., Springer Reference, Secaucus, NJ: Springer US, 2008. - S. Sridhar, S. Rao, and E. Halperin, "An efficient and accurate graph-based approach to detect population substructure," in
*Research in Computational Molecular Biology: Proc. 11th Annual Intl. Conf. (RECOMB 2007)*, T. Speed and H. Huang, Eds., Lecture Notes in Computer Science::Lecture Notes in Bioinformatics, Vol. 4453, Berlin, Germany: Springer-Verlag, 2007, pp. 503-517. - C. Daskalakis, C. Hill, A. Jaffe, R. Mihaescu, E. Mossel, and S. Rao, "Maximal accurate forests from distance matrices," in
*Research in Computational Molecular Biology: Proc. 10th Annual Intl. Conf. (RECOMB 2006)*, A. Apostolico, C. Guerra, S. Istrail, P. Pevzner, and M. Waterman, Eds., Lecture Notes in Bioinformatics, Vol. 3909, Berlin, Germany: Springer-Verlag, 2006, pp. 281-295.

## Articles in journals or magazines

- S. Arora, S. Rao, and U. Vazirani, "Geometry, flows, and graph-partitioning algorithms,"
*Communications ACM*, vol. 51, no. 10, pp. 96-105, Oct. 2008. - S. G. Kolliopoulos and S. Rao, "A nearly linear-time approximation scheme for the Euclidean $k$-median problem,"
*SIAM J. Computing*, vol. 37, no. 3, pp. 757-782, July 2007. - J. Fakcharoenphol, C. Harrelson, and S. Rao, "The k-traveling repairmen problem,"
*ACM Trans. on Algorithms: Special Issue on SODA 2002*, vol. 3, no. 1, pp. Art. 40, Feb. 2007. - K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed object location in a dynamic network,"
*Theory of Computing Systems*, vol. 37, no. 3, pp. 405-440, May 2004. - G. Even, J. S. Naor, S. Rao, and B. Schieber, "Divide-and-conquer approximation algorithms using spreading metrics,"
*J. 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,"
*J. ACM*, vol. 46, no. 6, pp. 787-832, Nov. 1999. - M. W. Goudreau, K. Lang, S. Rao, T. Suel, and T. Tsantilas, "Portable and efficient parallel computing using the BSP model,"
*IEEE Trans. Computers*, vol. 48, no. 7, pp. 670-689, July 1999. - A. V. Goldberg and S. Rao, "Beyond the flow decomposition barrier,"
*J. ACM*, vol. 45, no. 5, pp. 783-797, Sep. 1998. - 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.

## Articles in conference proceedings

- P. Biswal, J. R. Lee, and S. Rao, "Eigenvalue bounds, spectral partitioning, and metrical deformations via flows," in
*Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)*, Los Alamitos, CA: IEEE Computer Society, 2008. - K. Chaudhuri and S. Rao, "Learning mixtures of product distributions using correlations and independence," in
*Proc. 21st Annual Conf. on Learning Theory (COLT 2008)*, R. A. Servedio and T. Zhang, Eds., Madison, WI: Omnipress, 2008, pp. 9-20. - K. Chaudhuri and S. Rao, "Beyond Gaussians: Spectral methods for learning mixtures of heavy-tailed distributions," in
*Proc. 21st Annual Conf. on Learning Theory (COLT 2008)*, R. A. Servedio and T. Zhang, Eds., Madison, WI: Omnipress, 2008, pp. 21-32. - B. Awerbuch, R. Khandekar, and S. Rao, "Distributed algorithms for multicommodity flow problems via approximate steepest descent framework," in
*Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2007)*, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007, pp. 949-957. - K. Chaudhuri, E. Halperin, S. Rao, and S. Zhou, "A rigorous analysis of population stratification with limited data," in
*Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2007)*, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007, pp. 1046-1055. - R. Khandekar, S. Rao, and U. Vazirani, "Graph partitioning using single commodity flows," in
*Proc. 38th Annual ACM Symp. on Theory of Computing*, New York, NY: ACM Press, 2006, pp. 385-390. - S. Arora, S. Rao, and U. Vazirani, "Expander flows, geometric embeddings and graph partitioning," in
*Proc. 36th Annual ACM Symp. on Theory of Computing*, New York, NY: ACM Press, 2004, pp. 222-231. - K. Hildrum, J. D. Kubiatowicz, S. Ma, and S. Rao, "A note on the nearest neighbor in growth-restricted metrics," in
*Proc. 15th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2004)*, New York, NY/Philadelphia, PA: ACM/SIAM, 2004, pp. 560-561. - J. Fakcharoenphol, S. Rao, and K. Talwar, "A tight bound on approximating arbitrary metrics by tree metrics," in
*Proc. 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
*Proc. 14th Annual ACM Symp. on Parallel Algorithms and Architectures*, New York, NY: ACM Press, 2002, pp. 41-52. - S. Rao, "Small distortion and volume preserving embeddings for planar and Euclidean metrics," in
*Proc. 15th Annual Symp. on Computational Geometry*, New York, NY: ACM Press, 1999, pp. 300-306. - I. J. Cox, S. Rao, and Y. Zhong, ""Ratio regions": A technique for image segmentation," in
*Proc. 13th Intl. Conf. on Pattern Recognition*, Vol. 2, Los Alamitos, CA: IEEE Computer Society, 1996, pp. 557-564.

## Technical Reports

- K. Chen and S. Rao, "An Improved Frequent Items Algorithm with Applications to Web Caching," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-05-1383, 2005. [abstract]
- K. Hildrum, S. Ma, and S. Rao, "Randomized Rumor Spreading with Fewer Phone Calls," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-04-1329, June 2004. [abstract]
- K. Hildrum, J. Kubiatowicz, and S. Rao, "Another Way to Find the Nearest Neighbor in Growth-Restricted Metrics," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-03-1267, Aug. 2003. [abstract]
- K. Hildrum, J. D. Kubiatowicz, S. Rao, and B. Y. Zhao, "Distributed Data Location in a Dynamic Network," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-02-1178, April 2002. [abstract]

## Patents

- I. J. Cox and S. B. Rao, "Method for image segmentation by minimizing the ratio between the exterior boundary cost and the cost of the enclosed region," U.S. Patent 6,078,688. June 2000.
- S. B. Rao, "VLSI circuit layout method based on spreading functions and simulated annealing heuristics to minimize area," U.S. Patent 5,737,233. April 1998.
- Y. Li and S. Rao, "Optical mesh-connected bus interconnect for a computer," U.S. Patent 5,465,379. Nov. 1995.

## Masters Reports

- S. Rao and J. Hong, "Analysis of Hidden Markov Models and Support Vector Machines in Financial Applications," P. Bartlett, Ed., EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2010-63, May 2010. [abstract]
- N. Wu, "Preliminary Studies on de novo Assembly with Short Reads," S. Rao and Y. S. Song, Eds., EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2009-172, Dec. 2009. [abstract]