Faculty Publications - Satish Rao

Articles in journals or magazines

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.

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.

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.
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.
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.
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.