1 citations · 2 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
Peter Davies-Peck
The classic lower bound of Kuhn, Moscibroda and Wattenhofer [JACM 2016] states that approximate maximum matching and approximate vertex cover (among other problems) in the LOCAL mo…
cs.DS2025★ 1 cited
On the Locality of the Lovász Local Lemma
Peter Davies-Peck
The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of `bad events', each occurring with probability at most…
cs.DS2023★ 1 cited
Parallel Derandomization for Coloring
Sam Coy, Artur Czumaj, Peter Davies +1
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, designin…