Thomas P. Hayes

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Low-Distortion Clustering in Bounded Growth Graphs.

[BibT_eX]

[DOI]

Yi-Jun Chang

Proceedings of the Structural Information and Communication Complexity, 2025

Brief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

2024

Reconstruction of random geometric graphs: Breaking the Ω(r) distortion barrier.

[BibT_eX]

[DOI]

Eur. J. Comb., 2024

Brief Announcement: Low-Distortion Clustering in Bounded Growth Graphs.

[BibT_eX]

[DOI]

Yi-Jun Chang

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Fraud Detection for Random Walks.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Improved Reconstruction of Random Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Wake up and Join Me! an Energy-Efficient Algorithm for Maximal Matching in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Distributed Metropolis Sampler with Optimal Parallelism.

[BibT_eX]

[DOI]

Weiming Feng

Yitong Yin

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

On the Power of Choice for k-Colorability of Random Graphs.

[BibT_eX]

[DOI]

Diksha Gupta

Proceedings of the Approximation, 2021

2020

The Energy Complexity of BFS in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

A Scalable Algorithm for Multiparty Interactive Communication with Private Channels.

[BibT_eX]

[DOI]

Proceedings of the ICDCN 2020: 21st International Conference on Distributed Computing and Networking, 2020

2019

Fully-Asynchronous Distributed Metropolis Sampler with Optimal Speedup.

[BibT_eX]

[DOI]

Weiming Feng

Yitong Yin

CoRR, 2019

Multiparty Interactive Communication with Private Channels.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Improved Strong Spatial Mixing for Colorings on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Interactive communication with unknown noise rate.

[BibT_eX]

[DOI]

Inf. Comput., 2018

Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors).

[BibT_eX]

[DOI]

Weiming Feng

Yitong Yin

CoRR, 2018

Sampling Random Colorings of Sparse Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

The Energy Complexity of Broadcast.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Sending a Message with Unknown Noise.

[BibT_eX]

[DOI]

Proceedings of the 19th International Conference on Distributed Computing and Networking, 2018

Screaming Channels: When Electromagnetic Side Channels Meet Radio Transceivers.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018

2017

Medium access control schemes for flat mobile wireless sensor networks.

[BibT_eX]

[DOI]

Tom Hayes

IET Wirel. Sens. Syst., 2017

Distributed Computing with Channel Noise.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

2016

Codes, lower bounds, and phase transitions in the symmetric rendezvous problem.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Location aware sensor routing protocol for mobile wireless sensor networks.

[BibT_eX]

[DOI]

Tom Hayes

IET Wirel. Sens. Syst., 2016

Secure one-way interactive communication.

[BibT_eX]

[DOI]

CoRR, 2016

Secure Multiparty Interactive Communication with Unknown Noise Rate.

[BibT_eX]

[DOI]

CoRR, 2016

Robust Ad-hoc Sensor Routing (RASeR) protocol for mobile wireless sensor networks.

[BibT_eX]

[DOI]

Ad Hoc Networks, 2016

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Proactive Highly Ambulatory Sensor Routing (PHASeR) protocol for mobile wireless sensor networks.

[BibT_eX]

[DOI]

Tom Hayes

Pervasive Mob. Comput., 2015

2014

Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics.

[BibT_eX]

[DOI]

Cristopher Moore

CoRR, 2014

2013

Local uniformity properties for glauber dynamics on graph colorings.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2013

Block Coordinate Descent for Sparse NMF

[BibT_eX]

[DOI]

Proceedings of the 1st International Conference on Learning Representations, 2013

The Power of Choice for Random Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2011

Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2011

How Not to Win a Million Dollars: A Counterexample to a Conjecture of L. Breiman

[BibT_eX]

[DOI]

CoRR, 2011

Sparseness and a reduction from Totally Nonnegative Least Squares to SVM.

[BibT_eX]

[DOI]

Proceedings of the 2011 International Joint Conference on Neural Networks, 2011

2010

Liftings of Tree-Structured Markov Chains - (Extended Abstract).

[BibT_eX]

[DOI]

Alistair Sinclair

Proceedings of the Approximation, 2010

2009

The adwords problem: online keyword matching with budgeted bidders under random permutations.

[BibT_eX]

[DOI]

Nikhil R. Devanur

Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

The forgiving graph: a distributed data structure for low stretch under adversarial attack.

[BibT_eX]

[DOI]

Jared Saia

Amitabh Trehan

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2008

Minimizing average latency in oblivious routing.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The forgiving tree: a self-healing distributed data structure.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Stochastic Linear Optimization under Bandit Feedback.

[BibT_eX]

[DOI]

Sham M. Kakade

Proceedings of the 21st Annual Conference on Learning Theory, 2008

High-Probability Regret Bounds for Bandit Online Linear Optimization.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Randomly coloring planar graphs with fewer colors than the maximum degree.

[BibT_eX]

[DOI]

Juan Carlos Vera

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Online collaborative filtering with nearly optimal dynamic regret.

[BibT_eX]

[DOI]

Baruch Awerbuch

Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

The Price of Bandit Information for Online Optimization.

[BibT_eX]

[DOI]

Sham M. Kakade

Proceedings of the Advances in Neural Information Processing Systems 20, 2007

2006

How to Beat the Adaptive Multi-Armed Bandit

[BibT_eX]

[DOI]

CoRR, 2006

Robbing the bandit: less regret in online geometric optimization against an adaptive adversary.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A simple condition implying rapid mixing of single-site dynamics on spin systems.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

2005

Coupling with the stationary distribution and improved sampling for colorings and independent sets.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.

[BibT_eX]

[DOI]

László Babai

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Error limiting reductions between classification tasks.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning, 2005

A general lower bound for mixing of single-site dynamics on graphs.

[BibT_eX]

[DOI]

Alistair Sinclair

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

2004

Reductions Between Classification Tasks

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Variable length path coupling.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Randomly Coloring Constant Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Randomly coloring graphs of girth at least five.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A Non-Markovian Coupling for Randomly Sampling Colorings.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

2002

The Quantum Black-Box Complexity of Majority.

[BibT_eX]

[DOI]

Samuel Kutin

Dieter van Melkebeek

Algorithmica, 2002

1998

The Cost of the Missing Bit: Communication Complexity with Help.

[BibT_eX]

[DOI]

László Babai