Approximate Agreement (AA) is a fundamental primitive that, even in the presence of Byzantine faults, allows honest parties to obtain close (but not necessarily identical) outputs that lie within the range of their inputs. While the optimal round complexity of synchronous AA on real values is well understood, its extension to other input spaces has remained open, with fundamental questions regarding achievable resilience and round efficiency still unresolved.

In this paper, we present an efficient massively parallel approximation algorithm for the \(k\)-means problem. Specifically, we provide an MPC algorithm that computes a constant-factor approximation to an arbitrary \(k\)-means instance in \(O(\log \log n \cdot \log \log \log n)\) rounds. The algorithm uses \(O(n^{\sigma})\) bits of memory per machine, where \(\sigma \gt 0\) is a constant that can be made arbitrarily small. The global memory usage is \(O(n^{1+\varepsilon})\) bits for an arbitrarily small constant \(\varepsilon \gt 0\), and is thus only slightly superlinear. Recently, Czumaj, Gao, Jiang, Krauthgamer, and Veselý showed that a constant-factor bicriteria approximation can be computed in \(O(1)\) rounds in the MPC model. However, our algorithm is the first constant-factor approximation for the general \(k\)-means problem that runs in \(o(\log n)\) rounds in the MPC model.

Understanding the role of randomness when solving locally checkable labeling (LCL) problems in the LOCAL model has been one of the top priorities in the research on distributed graph algorithms in recent years. For LCL problems in bounded-degree graphs, it is known that randomness cannot help more than polynomially, except in one case: if the deterministic complexity of an LCL problem is in Ω(log n) and its randomized complexity is in o(log n), then the randomized complexity is guaranteed to be O(poly(log log n)) and it is even known to be O(log log n) in bounded-degree trees. However, the fundamental question of which problems with a deterministic complexity of Ω(log n) can be solved exponentially faster using randomization still remains wide open. We make a step towards answering this question by studying a simple, but natural class of LCL problems: so-called degree splitting problems. These problems come in two varieties: coloring problems where the edges of a graph have to be colored with 2 colors and orientation problems where each edge needs to be oriented. For an exact classification, it is most natural to consider the Δ-regular case (for Δ = O(1)), where we obtain the following results. - We exactly characterize the complexity of problems where the edges need to be colored with two colors, say red and blue. We show that for every y ∈ {0,… ,Δ-1}, the problem of red-blue coloring the edges such that every node of degree Δ has either y or y+1 red edges has randomized complexity O(log log n) in general graphs of maximum degree Δ. Any other problem, i.e., any problem that does not allow two consecutive red degrees, is already known to have randomized complexity Ω(log n) even in Δ-regular trees. We note that a set of edges F such that every node has either y or y+1 incident edges in F is also known as a {y,y+1}-factor of a graph. - For edge orientations, we show that for any two r₁ and r₂ such that r₁,r₂ ≤ Δ/2 and r₁+r₂ ≥ Δ/2, there are randomized algorithms with round complexities O(log log n) in trees and Õ(log⁴log n) in general graphs to compute an edge orientation such that all nodes have outdegree r₁ ± O(√{ΔlogΔ}) or Δ-r₂ ± O(√{ΔlogΔ}). Further, there exists a constant c > 0 such that for any 0 ≤ r₁+r₂ ≤ Δ/2, the problem of computing an edge orientation in which all outdegrees are either at most r₁-c⋅ √{Δ} or at least Δ-r₂+c⋅√{Δ} has randomized complexity Ω(log n) even in Δ-regular trees. While our results are cleanest to state for the Δ-regular case, all our algorithms naturally generalize to nodes of any degree d < Δ in general graphs of maximum degree Δ. All our algorithms also naturally generalize to the unbounded degree case and they then have a randomized complexity of Õ(Δ) ⋅ log log n (resp. Õ(Δ ⋅log⁴log n) for orienting general graphs).

Approximate Agreement (AA) is a key consensus primitive that allows honest parties to achieve close but not necessarily identical outputs, even in the presence of Byzantine faults. While optimal round complexity for synchronous AA on real values is well understood, its extension to other input spaces remains an open problem.

We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory.

We study the deterministic complexity of the $2$-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory. Linear MPC: We present a constant-round deterministic algorithm for the $2$-Ruling Set problem that matches the randomized round complexity recently settled by Cambus, Kuhn, Pai, and Uitto [DISC'23], and improves upon the deterministic $O(\log \log n)$-round algorithm by Pai and Pemmaraju [PODC'22]. Our main ingredient is a simpler analysis of CKPU's algorithm based solely on bounded independence, which makes its efficient derandomization possible. Sublinear MPC: We present a deterministic algorithm that computes a $2$-Ruling Set in $\tilde O(\sqrt{\log n})$ rounds deterministically. Notably, this is the first deterministic ruling set algorithm with sublogarithmic round complexity, improving on the $O(\log Δ+ \log \log^* n)$-round complexity that stems from the deterministic MIS algorithm of Czumaj, Davies, and Parter [TALG'21]. Our result is based on a simple and fast randomness-efficient construction that achieves the same sparsification as that of the randomized $\tilde O(\sqrt{\log n})$-round LOCAL algorithm by Kothapalli and Pemmaraju [FSTTCS'12].

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in $d$-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in $\widetilde{\mathcal{O}}(n^{5/3})$ time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time $\mathcal{O}(n^{2-δ})$ for some $δ>0$. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in $\mathbb{R}^3$ or congruent equilateral triangles in $\mathbb{R}^2$. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in $\mathbb{R}^2$. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in~$\mathbb{R}^{12}$, distinguishing between diameter 2 and 3 needs quadratic time (ruling out $(3/2-\varepsilon)$- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter $2$ and $3$ in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors.