Peter Davies-Peck

TCS Journal 2026 Journal Article

Parallel derandomization for coloring

• Sam Coy
• Artur Czumaj
• Peter Davies-Peck
• Gopinath Mishra

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 particularly challenging. In this work we consider this challenge, and design a novel framework for derandomizing algorithms for coloring-type problems in the Massively Parallel Computation (MPC) model with sublinear space. We give an application of this framework by showing that a recent ( d e g r e e + 1 ) -list coloring algorithm by Halldórsson, Kuhn, Nolin, and Tonoyan (STOC’22) in the LOCAL model of distributed computation can be translated to the MPC model and efficiently derandomized. Our algorithm runs in O(log log log n) rounds, which matches the complexity of the state of the art algorithm for the ( Δ + 1 ) -coloring problem.

STOC Conference 2025 Conference Paper

On the Locality of the Lovász Local Lemma

• Peter Davies-Peck

SODA Conference 2023 Conference Paper

Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring

• Peter Davies-Peck

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 with probability at most p and is independent of all but d other events, then under certain criteria on p and d, all of the bad events can be avoided with positive probability. While the original proof was existential, there has been much study on the algorithmic Lovász Local Lemma: that is, designing an algorithm which finds an assignment of the underlying random variables such that all the bad events are indeed avoided. Notably, the celebrated result of Moser and Tardos [JACM '10] also implied an efficient distributed algorithm for the problem, running in O (log 2 n ) rounds. For instances with low d, this was improved to O ( d 2 + log 0(1) log n ) by Fischer and Ghaffari [DISC '17], a result that has proven highly important in distributed complexity theory (Chang and Pettie [SICOMP '19]). We give an improved algorithm for the Lovász Local Lemma, providing a trade-off between the strength of the criterion relating p and d, and the distributed round complexity. In particular, in the same regime as Fischer and Ghaffari's algorithm, we improve the round complexity to. At the other end of the trade-off, we obtain a log O (1) log n round complexity for a substantially wider regime than previously known. As our main application, we also give the first log O (1) log n-round distributed algorithm for the problem of Δ + o(Δ)-edge coloring a graph of maximum degree Δ. This is an almost exponential improvement over previous results: no prior log o (1) n -round algorithm was known even for 2Δ — 2-edge coloring.

ICML Conference 2021 Conference Paper

Communication-Efficient Distributed Optimization with Quantized Preconditioners

• Foivos Alimisis
• Peter Davies-Peck
• Dan Alistarh

We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among $n$ different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have \emph{linear} dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton’s method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing faster convergence and reduced communication relative to previous methods.

ICLR Conference 2021 Conference Paper

New Bounds For Distributed Mean Estimation and Variance Reduction

• Peter Davies-Peck
• Vijaykrishna Gurunanthan
• Niusha Moshrefi
• Saleh Ashkboos
• Dan Alistarh

We consider the problem of distributed mean estimation (DME), in which $n$ machines are each given a local $d$-dimensional vector $\mathbf x_v \in \mathbb R^d$, and must cooperate to estimate the mean of their inputs $\mathbf \mu = \frac 1n\sum_{v = 1}^n \mathbf x_v$, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output $\mathbf \mu$, but $\mathbf \mu$ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under $\ell_2$-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor in $d$. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.