# Deterministic coloring algorithms in the LOCAL model

**Authors:** Dariusz R. Kowalski, Piotr Krysta  
**arXiv:** [1907.12857](https://arxiv.org/abs/1907.12857)  
**Date:** 2019-07-30  
**Summary page:** https://www.summarizepaper.com/en/paper/1907.12857v2/

## Key points

- Authors address the problem of bi-chromatic coloring of hypergraphs in the LOCAL distributed model
- Propose a deterministic algorithm with polylogarithmic communication rounds to solve the problem
- Algorithm represents an almost exponential improvement over previous deterministic local algorithms
- Findings extend beyond bi-chromatic coloring and are complete in the class of all locally checkable graph problems
- Implies deterministic local algorithms with polylogarithmic communication rounds for problems with efficient randomized algorithms
- Work also implies polylogarithmically efficient deterministic local algorithms for many other graph problems
- Presents a significant advancement in understanding and solving graph problems within the LOCAL model
- Addresses a fundamental open problem in the field and provides almost exponential improvements over existing solutions

## Summary

In the paper "Deterministic coloring algorithms in the LOCAL model," authors Dariusz R. Kowalski and Piotr Krysta address the problem of bi-chromatic coloring of hypergraphs in the LOCAL distributed model of computation. To fill this gap, they propose a deterministic algorithm that solves the bi-chromatic coloring problem with a polylogarithmic number of communication rounds. This algorithm represents an almost exponential improvement over previously known deterministic local algorithms for this problem. The significance of their findings extends beyond just solving the bi-chromatic coloring problem; it is known to be complete in the class of all locally checkable graph problems. As a result, their algorithm implies deterministic local algorithms with polylogarithmic communication rounds for all such problems where an efficient randomized algorithm exists. Furthermore, due to reductions by Ghaffari, Kuhn, and Maus (STOC 2017), their work also implies polylogarithmically efficient deterministic local algorithms for many other graph problems. Overall, this paper presents a significant advancement in understanding and solving graph problems within the LOCAL model of computation. It addresses one of the fundamental open problems in the field and provides almost exponential improvements over existing solutions.