Selected Publications
from 1998 to present
2006
"New Lower Bounds for Oblivious Routing in Undirected Graphs," 17th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2006), 2006, pp. 918927. (with M.T. Hajiaghayi, R.D. Kleinberg; and H. Raecke)
"Improved Lower and Upper Bounds for Universal TSP in Planar Metrics," 17th Annual ACMSIAM Symposium on
Discrete Algorithms (SODA 2006), 2006, pp.649658. (with M.T. Hajiaghayi and R.D. Kleinberg)
"On the maxflow mincut ratio for directed mulitcommodity flows," Journal of Theoretical Computer Science. 352(13) 2006, pp.31832. (with M.T. Hajiaghayi)
2005
"Oblivious Routing on NodeCapacitated and Directed Graphs", in Proceedings of the 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 782790 (with M.T. Hajiaghayi; R.D. Kleinberg; and H. Raecke)
"Online ClientServer Load Balancing Without Global Information," in Proceedings of the 16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2005, pp.197206 (with B. Awerbuch; M.T. Hajiaghayi; and R.D. Kleinberg)
"Oblivious routing in directed graphs with random demands," ACM Symposium on Theory of Computing (STOC), 2005, pp. 193201 (with M.T. Hajiahgayi; J.H. Kim; and H. Raecke).
2004
"The Challenges of Delivering Content and Applications on the Internet," Proc. of the 14th International Workshop on Research Issues on Data Engineering: Web Services for ECommerce and EGovernment Applications (RIDE'04), 2004, p. 65.
2003
"Fractal Merkle Tree Representation and Traversal", RSACT conference, 2003, pp. 314326 (with M. Jakobsson , S. Micali and M. Szydlo) .
"Consistent load balancing via spread minimization," Proc. of the thirtyfifth annual ACM symposium on Theory of computing, 2003, pp. 565574 (with R. Kleinberg).
"The Value of Knowing a Demand Curve: Bounds on Regret for Online PostedPrice Auctions," Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, p. 594 (with R. Kleinberg).
2001
"The Challenges of Delivering Content on
the Internet." PODS 2001.
"Guessing
secrets." SODA 2001, pp. 723726 (with Fan R. K. Chung and R.L. Graham).
"The Challenges of Delivering Content on
the Internet." WADS 2001, p. 338.
" Universalstability
results and performance bounds for greedy contentionresolution
protocols." JACM, 2001, Vol. 48, no.1, pp. 3969 (with M. Andrews, B. Awerbuch, A. Fernández, Z. Liu, and J.M. Kleinberg).
"Compression Using Efficient
Multicasting. JCSS, 2001, Vol. 63, no. 1. pp. 127145 (with M. Adler).
2000
"Tight Bounds on the Size of FaultTolerant Merging and Sorting Networks with Destructive Faults," SIAM J. Comput.,2000, Vol. 29, no. 1, pp. 258273 (with Y. Ma).
1999
"Automatic Methods for Hiding Latency in Parallel and Distributed Computation," SIAM J. Comput.,1999, Vol. 29, no. 2, pp. 615647 (with M. Andrews, P. T. Metaxas, and L. Zhang).
"Reconstructing a threedimensional model with arbitrary errors," J. ACM,1999, Vol. 46, no. 2, pp. 212235 (with B. Berger and J. Kleinberg).
"Tight Bounds for OnLine Tree Embeddings," SIAM J. Comput.,1999, Vol. 29, no. 2, pp. 474491 (with S. Bhatt, D. Greenberg, and P. Liu).
"Tight Analyses of Two Local Load Balancing Algorithms. SIAM J. Comput., Vol. 29, 1999, No. 1, pp. 2964, (with B. Ghosh, B. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. Richa, Robert E. Tarjan, and D. Zuckerman).
"Multicommodity maxflow mincut theorems and their use in designing approximation algorithms," J. ACM,1999, Vol. 46, no. 6, pp. 787832 (with S. Rao).
1998
"Hypercubic Sorting Networks," SIAM J. Comput. Vol. 27, 1998, no.1, pp.147 (with C. G. Plaxton).
"ProcessorRing Communication: A Tight Asymptotic Bound on Packet Waiting Times," SIAM J. Comput.Vol. 27, 1998, no. 5, pp. 12211236 (with E. G. Coffman Jr. and N. Kahale).
``Tight Analyses of Two Local Load Balancing Algorithms,'' SIAM J. Comput. Vol. 29, 1999, No. 1, pp. 2964, (with B. Ghosh, B. Maggs, S. Muthukrishnan, G. Plaxton, R. Rajaraman, A. Richa, R. Tarjan, and D. Zuckerman).
"On the Fault Tolerance of Some Popular BoundedDegree Networks," SIAM J. Comput.,Vol. 27, 1998, no. 5, pp.13031333 (with B. Maggs and R. Sitaraman).
For a list of Tom's publications, please refer to
the DBLP
Bibliography Server. For copies of Tom's complete Vitae, which
details his research papers, please contact his assistant at MIT,
Patrice Macaluso
