Thomas P. Hayes

82 papers A* 29A 5B 3Misc 2Journal 38Unranked 5
YearRankTypeTitle / Venue / Authors
2025 A* conf
A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs.
SODA
Varsha Dani, Thomas P. Hayes
2025 A* conf
Brief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks.
PODC
Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, Gopal Pandurangan
2025 A conf
Energy-Efficient Maximal Independent Sets in Radio Networks.
DISC
Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, Gopal Pandurangan
2025 J jnl
Energy-Efficient Maximal Independent Sets in Radio Networks.
CoRR
Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, Gopal Pandurangan
2025 B conf
Low-Distortion Clustering in Bounded Growth Graphs.
SIROCCO
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes
2025 J jnl
Optimal mixing via tensorization for random independent sets on arbitrary trees.
Comb. Probab. Comput.
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2024 A* conf
Brief Announcement: Low-Distortion Clustering in Bounded Growth Graphs.
PODC
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes
2024 A conf
Fraud Detection for Random Walks.
ITCS
Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia
2024 J jnl
Low-Distortion Clustering in Bounded Growth Graphs.
CoRR
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes
2024 J jnl
Reconstruction of random geometric graphs: Breaking the Ω(r) distortion barrier.
Eur. J. Comb.
Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore
2023 A conf
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees.
APPROX/RANDOM
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2023 J jnl
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees.
CoRR
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2023 J jnl
Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks.
Distributed Comput.
Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2022 J jnl
How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks.
CoRR
Varsha Dani, Thomas P. Hayes
2022 A conf
How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks.
DISC
Varsha Dani, Thomas P. Hayes
2022 A* conf
Improved Reconstruction of Random Geometric Graphs.
ICALP
Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore
2021 A* conf
Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks.
PODC
Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2021 A* conf
Distributed Metropolis Sampler with Optimal Parallelism.
SODA
Weiming Feng, Thomas P. Hayes, Yitong Yin
2021 J jnl
Improved Reconstruction of Random Geometric Graphs.
CoRR
Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore
2021 — conf
On the Power of Choice for k-Colorability of Random Graphs.
APPROX-RANDOM
Varsha Dani, Diksha Gupta, Thomas P. Hayes
2021 J jnl
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks.
CoRR
Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2021 A conf
Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks.
DISC
Varsha Dani, Aayush Gupta, Thomas P. Hayes, Seth Pettie
2020 Misc conf
A Scalable Algorithm for Multiparty Interactive Communication with Private Channels.
ICDCN
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
2020 A* conf
The Energy Complexity of BFS in Radio Networks.
PODC
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie
2020 J jnl
The Energy Complexity of BFS in Radio Networks.
CoRR
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Seth Pettie
2019 J jnl
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
SIAM J. Comput.
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
2019 J jnl
Fully-Asynchronous Distributed Metropolis Sampler with Optimal Speedup.
CoRR
Weiming Feng, Thomas P. Hayes, Yitong Yin
2019 — conf
Improved Strong Spatial Mixing for Colorings on Trees.
APPROX-RANDOM
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2019 J jnl
Improved Strong Spatial Mixing for Colorings on Trees.
CoRR
Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2019 A* conf
Multiparty Interactive Communication with Private Channels.
PODC
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
2018 J jnl
Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors).
CoRR
Weiming Feng, Thomas P. Hayes, Yitong Yin
2018 J jnl
Interactive communication with unknown noise rate.
Inf. Comput.
Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, Maxwell Young
2018 A* conf
Sampling Random Colorings of Sparse Random Graphs.
SODA
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2018 Misc conf
Sending a Message with Unknown Noise.
ICDCN
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
2018 A* conf
The Energy Complexity of Broadcast.
PODC
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie
2017 J jnl
Distributed Computing with Channel Noise.
IACR Cryptol. ePrint Arch.
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
2017 J jnl
Sampling Random Colorings of Sparse Random Graphs.
CoRR
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda
2017 J jnl
The Energy Complexity of Broadcast.
CoRR
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie
2016 J jnl
Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem.
CoRR
Varsha Dani, Thomas P. Hayes, Cristopher Moore, Alexander Russell
2016 J jnl
Codes, lower bounds, and phase transitions in the symmetric rendezvous problem.
Random Struct. Algorithms
Varsha Dani, Thomas P. Hayes, Cristopher Moore, Alexander Russell
2016 A* conf
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
FOCS
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
2016 J jnl
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
CoRR
Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin
2016 J jnl
Robust Ad-hoc Sensor Routing (RASeR) protocol for mobile wireless sensor networks.
Ad Hoc Networks
Thomas P. Hayes, Falah H. Ali
2016 J jnl
Secure Multiparty Interactive Communication with Unknown Noise Rate.
CoRR
Abhinav Aggarwal, Varsha Dani, Nico Döttling, Thomas P. Hayes, Jared Saia
2016 J jnl
Secure one-way interactive communication.
CoRR
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, Jared Saia
2015 J jnl
Randomly coloring planar graphs with fewer colors than the maximum degree.
Random Struct. Algorithms
Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda
2014 J jnl
Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics.
CoRR
Thomas P. Hayes, Cristopher Moore
2013 A* conf
Block Coordinate Descent for Sparse NMF
ICLR (Poster)
Vamsi K. Potluru, Sergey M. Plis, Jonathan Le Roux, Barak A. Pearlmutter, Vince D. Calhoun, Thomas P. Hayes
2013 J jnl
Local uniformity properties for glauber dynamics on graph colorings.
Random Struct. Algorithms
Thomas P. Hayes
2013 J jnl
Randomly coloring constant degree graphs.
Random Struct. Algorithms
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda
2013 — conf
The Power of Choice for Random Satisfiability.
APPROX-RANDOM
Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore
2012 J jnl
The Forgiving Graph: a distributed data structure for low stretch under adversarial attack.
Distributed Comput.
Thomas P. Hayes, Jared Saia, Amitabh Trehan
2012 J jnl
The Power of Choice for Random Satisfiability
CoRR
Varsha Dani, Josep Díaz, Thomas P. Hayes, Cristopher Moore
2011 J jnl
How Not to Win a Million Dollars: A Counterexample to a Conjecture of L. Breiman
CoRR
Thomas P. Hayes
2011 J jnl
Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem.
Discret. Math. Theor. Comput. Sci.
Thomas P. Hayes
2011 B conf
Sparseness and a reduction from Totally Nonnegative Least Squares to SVM.
IJCNN
Vamsi K. Potluru, Sergey M. Plis, Shuang Luan, Vince D. Calhoun, Thomas P. Hayes
2010 — conf
Liftings of Tree-Structured Markov Chains - (Extended Abstract).
APPROX-RANDOM
Thomas P. Hayes, Alistair Sinclair
2009 A* conf
The adwords problem: online keyword matching with budgeted bidders under random permutations.
EC
Nikhil R. Devanur, Thomas P. Hayes
2009 A* conf
The forgiving graph: a distributed data structure for low stretch under adversarial attack.
PODC
Thomas P. Hayes, Jared Saia, Amitabh Trehan
2008 A* conf
High-Probability Regret Bounds for Bandit Online Linear Optimization.
COLT
Peter L. Bartlett, Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Alexander Rakhlin, Ambuj Tewari
2008 A* conf
Minimizing average latency in oblivious routing.
SODA
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
2008 A* conf
Stochastic Linear Optimization under Bandit Feedback.
COLT
Varsha Dani, Thomas P. Hayes, Sham M. Kakade
2007 B conf
Online collaborative filtering with nearly optimal dynamic regret.
SPAA
Baruch Awerbuch, Thomas P. Hayes
2007 A* conf
Randomly coloring planar graphs with fewer colors than the maximum degree.
STOC
Thomas P. Hayes, Juan Carlos Vera, Eric Vigoda
2007 — conf
The Price of Bandit Information for Online Optimization.
NIPS
Varsha Dani, Thomas P. Hayes, Sham M. Kakade
2007 J jnl
Variable length path coupling.
Random Struct. Algorithms
Thomas P. Hayes, Eric Vigoda
2006 A* conf
A simple condition implying rapid mixing of single-site dynamics on spin systems.
FOCS
Thomas P. Hayes
2006 J jnl
How to Beat the Adaptive Multi-Armed Bandit
CoRR
Varsha Dani, Thomas P. Hayes
2006 A* conf
Robbing the bandit: less regret in online geometric optimization against an adaptive adversary.
SODA
Varsha Dani, Thomas P. Hayes
2005 A* conf
A general lower bound for mixing of single-site dynamics on graphs.
FOCS
Thomas P. Hayes, Alistair Sinclair
2005 A* conf
Coupling with the stationary distribution and improved sampling for colorings and independent sets.
SODA
Thomas P. Hayes, Eric Vigoda
2005 A* conf
Error limiting reductions between classification tasks.
ICML
Alina Beygelzimer, Varsha Dani, Thomas P. Hayes, John Langford, Bianca Zadrozny
2005 A* conf
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.
SODA
László Babai, Thomas P. Hayes
2004 A* conf
Randomly Coloring Constant Degree Graphs.
FOCS
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda
2004 J jnl
Randomly coloring constant degree graphs
Electron. Colloquium Comput. Complex.
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda
2004 J jnl
Reductions Between Classification Tasks
Electron. Colloquium Comput. Complex.
Alina Beygelzimer, Varsha Dani, Thomas P. Hayes, John Langford
2004 A* conf
Variable length path coupling.
SODA
Thomas P. Hayes, Eric Vigoda
2003 A* conf
A Non-Markovian Coupling for Randomly Sampling Colorings.
FOCS
Thomas P. Hayes, Eric Vigoda
2003 A* conf
Randomly coloring graphs of girth at least five.
STOC
Thomas P. Hayes
2002 J jnl
The Quantum Black-Box Complexity of Majority.
Algorithmica
Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek
2001 J jnl
The Cost of the Missing Bit: Communication Complexity with Help.
Comb.
László Babai, Thomas P. Hayes, Peter G. Kimmel
1998 A* conf
The Cost of the Missing Bit: Communication Complexity with Help.
STOC
László Babai, Thomas P. Hayes, Peter G. Kimmel