Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie.
Also available on arXiv [cs.DS, cs.DC].

The Power of Choice for Random Satisfiability
Varsha Dani, Josep Diaz, Thomas Hayes, Cristopher Moore.
arXiv:1211.6997 [cs.CC]

Randomly Coloring Constant Degree Graphs
Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda.
Random Structures and Algorithms, 2012.

The Forgiving Graph: A distributed data structure for low stretch under adversarial attack
Thomas P. Hayes, Jared Saia and Amitabh Trehan.
Distributed Computing, 2012.
Extended Abstract in: Proc. 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2009).

Online Matchings via Randomized Queueing
T. P. Hayes
Manuscript, December 2011.

How Not  to Win a Million Dollars: A Counterexample to a Conjecture of L. Breiman
T. P. Hayes
Manuscript, arXiv:1112.0829 [math.PR], 2011.

Sparseness and a Reduction from Totally Nonnegative Least Squares to SVM.
V. Potluru, S. Plis, S. Luan, V. Calhoun and T. P. Hayes
In: International Joint Conference on Neural Networks (IJCNN), 2011.

Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem.
Thomas P. Hayes.
To appear in: Discrete Mathematics and Theoretic Computer Science.

Liftings of Tree-Structured Markov Chains (Extended Abstract)
Thomas P. Hayes and Alistair Sinclair.
In: Proceedings of APPROX-RANDOM, 2010, 602-616.

The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations
Nikhil R. Devanur and Thomas P. Hayes
In: Proc. 10th Annual ACM Conference on Electronic Commerge (EC 2009).

Local Uniformity Properties for Glauber Dynamics on Graph Colorings
Thomas P. Hayes
Submitted to journal.

The Forgiving Tree: A Self-Healing Distributed Data Structure.
Thomas P. Hayes, Navin Rustagi, Jared Saia and Amitabh Trehan.
In: Proc. 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2008). Also 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 proceedings of COLT 2008.

Stochastic Linear Optimization Under Bandit Feedback.
Varsha Dani, Thomas P. Hayes and Sham M. Kakade.
In proceedings of COLT 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
Thomas P. Hayes and Eric Vigoda.
Random Structures and Algorithms 31/3 (2007) 251–272.
Extended abstract in: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), 103--110.

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.