Selected Publications from 1998 to present

2006

"New Lower Bounds for Oblivious Routing in Undirected Graphs," 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 2006, pp. 918-927. (with M.T. Hajiaghayi, R.D. Kleinberg; and H. Raecke)

"Improved Lower and Upper Bounds for Universal TSP in Planar Metrics," 17th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 2006), 2006, pp.649-658. (with M.T. Hajiaghayi and R.D. Kleinberg)

"On the max-flow min-cut ratio for directed mulitcommodity flows," Journal of Theoretical Computer Science. 352(1-3) 2006, pp.318-32. (with M.T. Hajiaghayi)

2005

"Oblivious Routing on Node-Capacitated and Directed Graphs", in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 782-790 (with M.T. Hajiaghayi; R.D. Kleinberg; and H. Raecke)

"Online Client-Server Load Balancing Without Global Information," in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp.197-206 (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. 193-201 (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 E-Commerce and E-Government Applications (RIDE'04), 2004, p. 65.

2003

"Fractal Merkle Tree Representation and Traversal", RSA-CT conference, 2003, pp. 314-326 (with M. Jakobsson , S. Micali and M. Szydlo) .

"Consistent load balancing via spread minimization," Proc. of the thirty-fifth annual ACM symposium on Theory of computing, 2003, pp. 565-574 (with R. Kleinberg).

"The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price 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. 723-726 (with Fan R. K. Chung and R.L. Graham).

"The Challenges of Delivering Content on the Internet." WADS 2001, p. 338.

" Universal-stability results and performance bounds for greedy contention-resolution protocols." JACM, 2001, Vol. 48, no.1, pp. 39-69 (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. 127-145 (with M. Adler).

2000

"Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults," SIAM J. Comput.,2000, Vol. 29, no. 1, pp. 258-273 (with Y. Ma).

1999

"Automatic Methods for Hiding Latency in Parallel and Distributed Computation," SIAM J. Comput.,1999, Vol. 29, no. 2, pp. 615-647 (with M. Andrews, P. T. Metaxas, and L. Zhang).

"Reconstructing a three-dimensional model with arbitrary errors," J. ACM,1999, Vol. 46, no. 2, pp. 212-235 (with B. Berger and J. Kleinberg).

"Tight Bounds for On-Line Tree Embeddings," SIAM J. Comput.,1999, Vol. 29, no. 2, pp. 474-491 (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. 29-64, (with B. Ghosh, B. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. Richa, Robert E. Tarjan, and D. Zuckerman).

"Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms," J. ACM,1999, Vol. 46, no. 6, pp. 787-832 (with S. Rao).

1998

"Hypercubic Sorting Networks," SIAM J. Comput. Vol. 27, 1998, no.1, pp.1-47 (with C. G. Plaxton).

"Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times," SIAM J. Comput.Vol. 27, 1998, no. 5, pp. 1221-1236 (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. 29-64, (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 Bounded-Degree Networks," SIAM J. Comput.,Vol. 27, 1998, no. 5, pp.1303-1333 (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