אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We consider graph coloring and related problems in the distributed message-passing model. **Locally-iterative** algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1-hop neighborhood. In STOC'93 Szegedy and Vishwanathan showed that any locally-iterative (\Delta + 1)-coloring algorithm requires Omega(\Delta \log \Delta + \log^* n) rounds, unless there exists "a very special type of coloring that can be very efficiently reduced".

No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms, and to explore other approaches to the coloring problem. The latter gave rise to faster algorithms, but their heavy machinery which is of non-locally-iterative nature made them far less suitable to various settings. In this work we devise the aforementioned special type of coloring. Specifically, we devise a locally-iterative (\Delta + 1)-coloring algorithm with running time O(\Delta + \log^* n), i.e., **below** Szegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing and bandwidth-restricted settings. This includes the following results.

1) We obtain self-stabilizing distributed algorithms for (\Delta + 1)-vertex-coloring, (2\Delta - 1)-edge-coloring, maximal independent set and maximal matching with O(\Delta + \log^* n) time. This significantly improves previously-known results that have O(n) or larger running times.

2) We devise a (2\Delta - 1)-edge-coloring algorithm in the CONGEST model with O(\Delta + \log^* n) time and in the Bit-Round model with O(\Delta + \log n) time. The factors of \log^* n and \log n are unavoidable in the CONGEST and Bit-Round models, respectively. Previously-known algorithms had superlinear dependency on \Delta for (2\Delta - 1)-edge-coloring in these models.

3) We obtain n arbdefective coloring algorithm with running time O(\sqrt \Delta + \log^* n). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it in order to compute a proper (1 + \epsilon)\Delta-coloring within O(\sqrt \Delta + \log^* n) time, and (\Delta + 1)-coloring within O(\sqrt {\Delta \log \Delta} \log^* \Delta + \log^* n) time. This improves the recent state-of-the-art bounds of Barenboim from PODC'15 and Fraigniaud et al. from FOCS'16 by polylogarithmic factors.

4) Our algorithms are applicable to the SET-LOCAL model (introduced by Hefetz et al.) (also known as the weak LOCAL model). In this model a relatively strong lower bound of \Omega(\Delta^{1/3}) is known for (\Delta + 1)-coloring. However, most of the coloring algorithms do not work in this model. We obtain the first linear-in-\Delta-time algorithms that work also in this model.

Joint work with Leonid Barenboim and Uri Goldenberg.