Skip to main content

Research Repository

Advanced Search

Outputs (12)

On the Locality of the Lovász Local Lemma (2025)
Presentation / Conference Contribution
Davies-Peck, P. (2025, June). On the Locality of the Lovász Local Lemma. Presented at 57th Annual ACM Symposium on Theory of Computing (STOC '25), Prague

The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set
of underlying random variables, can be avoided... Read More about On the Locality of the Lovász Local Lemma.

Parallel Derandomization for Coloring (2024)
Presentation / Conference Contribution
Coy, S., Czumaj, A., Davies-Peck, P., & Mishra, G. (2024, May). Parallel Derandomization for Coloring. Presented at 38th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2024), San Francisco

Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designing efficient deterministic algorithms for these problems has been found... Read More about Parallel Derandomization for Coloring.

Component stability in low-space massively parallel computation (2024)
Journal Article
Czumaj, A., Davies-Peck, P., & Parter, M. (2024). Component stability in low-space massively parallel computation. Distributed Computing, 37(1), 35-64. https://doi.org/10.1007/s00446-024-00461-9

In this paper, we study the power and limitations of component-stable algorithms in the low-space model of massively parallel computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algo... Read More about Component stability in low-space massively parallel computation.

Optimal (degree+1)-Coloring in Congested Clique (2023)
Presentation / Conference Contribution
Coy, S., Czumaj, A., Davies, P., & Mishra, G. (2023, July). Optimal (degree+1)-Coloring in Congested Clique. Presented at ICALP 2023: 50th EATCS International Colloquium on Automata, Languages and Programming, Paderborn, Germany

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u) + 1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list co... Read More about Optimal (degree+1)-Coloring in Congested Clique.

Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization (2023)
Presentation / Conference Contribution
Davies, P. (2023, June). Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization. Presented at PODC 2023: ACM Symposium on Principles of Distributed Computing, Orlando, Florida

In the study of radio networks, the tasks of broadcasting (propagating a message throughout the network) and leader election (having the network agree on a node to designate ‘leader’) are two of the most fundamental global problems, and have a long h... Read More about Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization.

Optimal Message-Passing with Noisy Beeps (2023)
Presentation / Conference Contribution
Davies, P. (2023, June). Optimal Message-Passing with Noisy Beeps. Presented at PODC 2023: ACM Symposium on Principles of Distributed Computing, Orlando, Florida

Beeping models are models for networks of weak devices, such as sensor networks or biological networks. In these networks, nodes are allowed to communicate only via emitting beeps: unary pulses of energy. Listening nodes only the capability of carrie... Read More about Optimal Message-Passing with Noisy Beeps.

Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring (2023)
Presentation / Conference Contribution
Davies, P. (2023, January). Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. Presented at ACM-SIAM Symposium on Discrete Algorithms (SODA23), Florence, Italy

The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n ‘bad events’, each of which occurs wit... Read More about Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring.

Asynchronous Decentralized SGD with Quantized and Local Updates (2021)
Presentation / Conference Contribution
Nadiradze, G., Sabour, A., Davies, P., Li, S., & Alistarh, D. (2021, December). Asynchronous Decentralized SGD with Quantized and Local Updates. Presented at Thirty-Fifth Annual Conference on Neural Information Processing Systems (NeurIPS 2021), Online

Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-block... Read More about Asynchronous Decentralized SGD with Quantized and Local Updates.

New Bounds For Distributed Mean Estimation and Variance Reduction (2021)
Presentation / Conference Contribution
Davies, P., Gurunathan, V., Moshrefi, N., Ashkboos, S., & Alistarh, D. (2021, May). New Bounds For Distributed Mean Estimation and Variance Reduction. Presented at 9th International Conference on Learning Representations (ICLR), Vienna, Austria

We consider the problem of distributed mean estimation (DME), in which n machines are each given a local d-dimensional vector x v ∈ R d , and must cooperate to estimate the mean of their inputs µ = 1 n n v=1 x v , while minimizing total communication... Read More about New Bounds For Distributed Mean Estimation and Variance Reduction.