Distributed algorithms, the Lovász local lemma, and descriptive combinatorics

DOI10.1007/s00222-023-01188-3zbMath1517.05049arXiv2004.04905WikidataQ124805685 ScholiaQ124805685MaRDI QIDQ6107878

Anton Bernshteyn

Publication date: 28 June 2023

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.04905

zbMATH Keywords

standard Borel spacesdistributed coloring algorithmssymmetric Lovász local lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (2)

Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring graphs when the number of colours is almost the maximum degree
• Perfect matchings as IID factors on non-amenable groups
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Borel chromatic numbers
• The list chromatic number of graphs with small clique number
• Asymptotically the list colouring constants are 1
• Topics in orbit equivalence
• Hyperfiniteness and Borel combinatorics
• Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Distributed coloring in sparse graphs with fewer colors
• Distributed coloring algorithms for triangle-free graphs
• A bound on measurable chromatic numbers of locally finite Borel graphs
• Countable abelian group actions and hyperfinite equivalence relations
• A Note on Vertex List Colouring
• A determinacy approach to Borel combinatorics
• Graph Theory
• Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
• A constructive proof of the general lovász local lemma
• An algorithmic approach to the Lovász local lemma. I
• Locality in Distributed Graph Algorithms
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• A Time Hierarchy Theorem for the LOCAL Model
• On a list coloring conjecture of Reed
• On Brooks' Theorem for Sparse Graphs
• What Can be Computed Locally?
• Bernoulli actions are weakly contained in any free action
• Weak containment of measure-preserving group actions
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Unfriendly colorings of graphs with finite average degree
• Orienting Borel graphs
• Improved Distributed Delta-Coloring
• LCL Problems on Grids
• BROOKS’ THEOREM FOR MEASURABLE COLORINGS
• Distributed algorithms for the Lovász local lemma and graph coloring
• Graph colouring and the probabilistic method

This page was built for publication: Distributed algorithms, the Lovász local lemma, and descriptive combinatorics