The Forgiving Tree: A Self-Healing Distributed Data Structure.
Thomas P. Hayes, Navin Rustagi, Jared Saia and Amitabh Trehan.
In submission. Preliminary version available on Arxiv

High Probability Regret Bounds for Online Linear Optimization.
Peter Bartlett, Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Alexander Rakhlin, and Ambuj Tewari.
In submission, 2008.

Stochastic Linear Optimization Under Bandit Feedback.
Varsha Dani, Thomas P. Hayes and Sham M. Kakade.
In submission, 2008.

Minimizing Average Latency in Oblivious Routing
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Racke, and Jaikumar Radhakrishnan
In: Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).

The Price of Bandit Information for Online Linear Optimization.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade.
In Proceedings of the 21st Annual Conference on Neural Information Processing Systems (NIPS 2007).

Randomly coloring planar graphs with fewer colors than the maximum degree.
Thomas P. Hayes, Juan C. Vera and Eric Vigoda.
In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007) 450--459. Extended version on Arxiv

Online collaborative filtering with nearly optimal dynamic regret.
Baruch Awerbuch and Thomas P. Hayes. In Proceedings of SPAA 2007.

A simple condition implying rapid mixing of single-site dynamics on spin systems. Download: PDF
Thomas P. Hayes.
In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 39-46.

The probability of generating the symmetric group when one of the generators is random. Download: PDF
László Babai and Thomas P. Hayes.
Publicationes Mathematicae Debrecen 69/3 (2006), 271-280.

Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. Download: PDF PS DVI
Varsha Dani and Thomas P. Hayes.
In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 937-943.

A general lower bound for mixing of single-site dynamics on graphs. Download: from ArXiv
Thomas P. Hayes and Alistair Sinclair.
Annals of Applied Probability, Volume 17, Number 3 (2007), 931-952.
Extended abstract in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005) 511-520.

Error limiting reductions between classification tasks. Download: PDF PS DVI
Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford and Bianca Zadrozny.
In: Proc. 22nd International Conference on Machine Learning (ICML 2005), ACM

Near-independence of permutations and an almost-sure polynomial bound on the diameter of the symmetric group. Download: PDF PS DVI
László Babai and Thomas P. Hayes.
Preliminary version in: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), 1057--1066.

Coupling with the Stationary Distribution and Improved Sampling for Colorings and Independent Sets. Download: PDF
Thomas P. Hayes and Eric Vigoda.
Annals of Applied Probability 16, no. 3 (2006) 1297-1318.
An extended abstract appeared in: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) 971-979.

Randomly coloring constant degree graphs. Download: PDF PS DVI
Martin Dyer, Alan Frieze, Thomas P. Hayes and Eric Vigoda.
Extended abstract in: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), 582--589

Variable Length Path Coupling. Download: PDF PS DVI
Thomas P. Hayes and Eric Vigoda.
Extended abstract in: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), 103--110.
Full version submitted to Random Structures and Algorithms

A Non-Markovian Coupling for Randomly Sampling Colorings. Download: PDF PS DVI
Thomas P. Hayes and Eric Vigoda.
Extended abstract in: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), 618--627

Randomly coloring graphs of girth at least five. Download: PDF PS DVI
Thomas P. Hayes.
Extended abstract in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003) 269-278.
Received the "Danny Lewin best student paper" award.

The truncated coin flips martingale maximizes escape probability. Download: PDF PS DVI
Thomas P. Hayes.
Manuscript, February 2003.

A Large-Deviation Inequality for Vector-valued Martingales. Download: PDF PS DVI
Thomas P. Hayes.
Submitted to Combinatorics, Probability and Computing.

On the Quantum Black-Box Complexity of Majority. Download: PDF PS DVI
Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek.
Algorithmica 34 (2002) 480-501. (Special issue for selected papers on quantum information processing.)

Separating the k-party communication hierarchy: an application of the Zarankiewicz problem. Download: PDF PS DVI
Thomas P. Hayes.
Manuscript, November 2001.

The Cost of the Missing Bit: Communication Complexity with Help. Download: PDF PS DVI
László Babai, Thomas P. Hayes, Peter Kimmel.
Combinatorica 21 (4) (2001) 455-488.
Preliminary version in: Proc. 30th Annual ACM Symposium on Theory of Computing (STOC 1998) 673--682.