English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove several new tight distributed lower bounds for classic symmetrybreaking graph problems. As a basic tool, we first provide a new insightfulproof that any deterministic distributed algorithm that computes a$\Delta$-coloring on $\Delta$-regular trees requires $\Omega(\log_\Delta n)$rounds and any randomized algorithm requires $\Omega(\log_\Delta\log n)$rounds. We prove this result by showing that a natural relaxation of the$\Delta$-coloring problem is a fixed point in the round elimination framework.  As a first application, we show that our $\Delta$-coloring lower bound proofdirectly extends to arbdefective colorings. We exactly characterize whichvariants of the arbdefective coloring problem are "easy", and which of theminstead are "hard". As a second application, which we see as our maincontribution, we use the structure of the fixed point as a building block toprove lower bounds as a function of $\Delta$ for a large class of distributedsymmetry breaking problems. For example, we obtain a tight lower bound for thefundamental problem of computing a $(2,\beta)$-ruling set. This is anexponential improvement over the best existing lower bound for the problem,which was proven in [FOCS '20]. Our lower bound even applies to a much moregeneral family of problems that allows for almost arbitrary combinations ofnatural constraints from coloring problems, orientation problems, andindependent set problems, and provides a single unified proof for known and newlower bound results for these types of problems.  Our lower bounds as a function of $\Delta$ also imply lower bounds as afunction of $n$. We obtain, for example, that maximal independent set, ontrees, requires $\Omega(\log n / \log \log n)$ rounds for deterministicalgorithms, which is tight.

Distributed $\Delta$-Coloring Plays Hide-and-Seek