ﻻ يوجد ملخص باللغة العربية
We present new randomized algorithms that improve the complexity of the classic $(Delta+1)$-coloring problem, and its generalization $(Delta+1)$-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an $O(1)$-round randomized algorithm for $(Delta+1)$-list coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the $O(log^ast Delta)$-round randomized algorithms of Parter and Su [DISC18] and $O((loglog Delta)cdot log^ast Delta)$-round randomized algorithm of Parter [ICALP18]. Massively Parallel Computation: We present a $(Delta+1)$-list coloring algorithm with round complexity $O(sqrt{loglog n})$ in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of $O(n^{alpha})$ per machine, for any desirable constant $alpha>0$, and a total memory of $widetilde{O}(m)$, where $m$ is the size of the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, an $O(1)$-round algorithm was given very recently by Assadi et al. [SODA19]. Centralized Local Computation: We show that $(Delta+1)$-list coloring can be solved with $Delta^{O(1)} cdot O(log n)$ query complexity, in the centralized local computation model. The previous state-of-the-art for $(Delta+1)$-list coloring in the centralized local computation model are based on simulation of known LOCAL algorithms.
We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA19] states that in every $n$-vertex graph $G$ with maximum degree $Delta$, sampling $O(log{n})$ colors per each vertex independently from $Delta+1$ colors almost certainly allow
We consider a decentralized graph coloring model where each vertex only knows its own color and whether some neighbor has the same color as it. The networking community has studied this model extensively due to its applications to channel selection,
We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lov{a}sz Local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld et al.~cite{Ronitt} that have received a lot of attention in recent
We consider the problem of finding lower bounds on the I/O complexity of arbitrary computations in a two level memory hierarchy. Executions of complex computations can be formalized as an evaluation order over the underlying computation graph. Howeve