Outputs (4)

Optimal (degree+1)-Coloring in Congested Clique (2023)
Presentation / Conference Contribution
Coy, S., Czumaj, A., Davies, P., & Mishra, G. (2023). Optimal (degree+1)-Coloring in Congested Clique. In K. Etessami, U. Feige, & G. Puppis (Eds.), 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (99:1-99:20). https://doi.org/10.4230/LIPIcs.ICALP.2023.46

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). Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization. . https://doi.org/10.1145/3583668.3594595

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). Optimal Message-Passing with Noisy Beeps. . https://doi.org/10.1145/3583668.3594594

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). Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (4273-4295). https://doi.org/10.1137/1.9781611977554.ch163

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.