23 citations · 76 across the 15 of their papers we have counts for
17 papers
Optimal (degree+1)-Coloring in Congested Clique
Sam Coy, Artur Czumaj, Peter Davies +1
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node of degree is assigned a palette of colors, and the goal is to…
Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
Peter Davies
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 `leade…
Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
Peter Davies
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 fo…
Collecting Coupons is Faster with Friends
Dan Alistarh, Peter Davies
In this note, we introduce a distributed twist on the classic coupon collector problem: a set of collectors wish to each obtain a set of coupons; for this, they can each sa…
Distributed Principal Component Analysis with Limited Communication
Foivos Alimisis, Peter Davies, Bart Vandereycken +1
We study efficient distributed algorithms for the fundamental problem of principal component analysis and leading eigenvector computation on the sphere, when the data are randomly…
Component Stability in Low-Space Massively Parallel Computation
Artur Czumaj, Peter Davies, Merav Parter
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) intr…
Communication-Efficient Distributed Optimization with Quantized Preconditioners
Foivos Alimisis, Peter Davies, 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 differ…
Simple, Deterministic, Constant-Round Coloring in the Congested Clique
Artur Czumaj, Peter Davies, Merav Parter
We settle the complexity of the -coloring and -list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems r…
New Bounds For Distributed Mean Estimation and Variance Reduction
Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi +2
We consider the problem of distributed mean estimation (DME), in which machines are each given a local -dimensional vector , and must cooperate to esti…
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
Artur Czumaj, Peter Davies, Merav Parter
The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (t…
Asynchronous Decentralized SGD with Quantized and Local Updates
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies +2
Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To t…
Randomized Communication Without Network Knowledge
Artur Czumaj, Peter Davies
Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is of…
Deterministic Blind Radio Networks
Artur Czumaj, Peter Davies
Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fun…
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
Artur Czumaj, Peter Davies
We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision d…
Deterministic Communication in Radio Networks
Artur Czumaj, Peter Davies
In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad-hoc radio networks with unknown topology: broadcastin…
Leader Election in Multi-Hop Radio Networks
Artur Czumaj, Peter Davies
In this paper we present a framework for leader election in multi-hop radio networks which yield randomized leader election algorithms taking in expec…
Communicating with Beeps
Artur Czumaj, Peter Davies
The \emph{beep model} is a very weak communications model in which devices in a network can communicate only via beeps and silence. As a result of its weak assumptions, it has broa…