Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms

DOI10.1016/j.aim.2023.108895OpenAlexW3131716689MaRDI QIDQ2684542

Anton Bernshteyn

Publication date: 16 February 2023

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Lovász local lemmaweak containmentlocal algorithmscontinuous combinatorics

Mathematics Subject Classification ID

Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15) Symbolic dynamics (37B10) Distributed algorithms (68W15) Infinite graphs (05C63)

Related Items (max. 100)

Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Equivariant maps to subshifts whose points have small stabilizers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Borel structurability on the 2-shift of a countable group
• Borel chromatic numbers
• Realization of aperiodic subshifts and uniform densities in groups
• Building large free subshifts using the Local Lemma
• Hyperfiniteness and Borel combinatorics
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Minimal dynamical systems and approximate conjugacy
• A determinacy approach to Borel combinatorics
• A coloring property for countable groups
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• Bernoulli actions are weakly contained in any free action
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Orienting Borel graphs
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• A lower bound for the distributed Lovász local lemma
• Group Colorings and Bernoulli Subflows
• LCL Problems on Grids
• Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma

This page was built for publication: Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms