Author name cluster

Sam Coy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

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.

Details DOI

TCS Journal 2024 Journal Article

Routing schemes for hybrid communication networks

Sam Coy
Artur Czumaj
Christian Scheideler
Philipp Schneider
Julian Werthmann

We consider the problem of computing routing schemes in the HYBRID model of distributed computing where nodes have access to two fundamentally different communication modes. In this problem nodes have to compute small labels and routing tables that allow for efficient routing of messages in the local network, which typically offers the majority of the throughput. Recent work has shown that using the HYBRID model admits a significant speed-up compared to what would be possible if either communication mode were used in isolation. Nonetheless, if general graphs are used as the input graph the computation of routing schemes still takes polynomial rounds in the HYBRID model. We bypass this lower bound by restricting the local graph to unit-disc-graphs and solve the problem deterministically with running time O ( | H | 2 + log ⁡ n ), label size O ( log ⁡ n ), and size of routing tables O ( | H | 2 ⋅ log ⁡ n ) where | H | is the number of “radio holes” in the network. Our work builds on recent work by Coy et al. , who obtain this result in the much simpler setting where the input graph has no radio holes. We develop new techniques to achieve this, including a decomposition of the local graph into path-convex regions, where each region contains a shortest path for any pair of nodes in it.

Details DOI

STOC Conference 2022 Conference Paper

Deterministic massively parallel connectivity

Sam Coy
Artur Czumaj

We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G . We consider the MPC with low local space , allowing each machine to store only Θ( n δ ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O (log D + loglog n ) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O (log n ) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O (log D + loglog n ) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D ≥ log 1+Ω(1) n ), by showing a related conditional hardness of Ω(log D ) MPC rounds for the entire spectrum of D , covering a particularly interesting range when D ≤ O (log n ).

Details