pith. sign in

arxiv: 1605.04877 · v2 · pith:RE6S5IQSnew · submitted 2016-05-16 · 🧮 math.CO · math.DS· math.PR

Borel version of the Local Lemma

Endre Cs\'oka , {\L}ukasz Grabowski , Andr\'as M\'ath\'e , Oleg Pikhurko , Konstantinos Tyros This is my paper
classification 🧮 math.CO math.DSmath.PR
keywords borellemmalocalversionalgorithmassignmentassumptionsbits
0
0 comments X
read the original abstract

We prove a Borel version of the local lemma, i.e. we show that, under suitable assumptions, if the set of variables in the local lemma has a structure of a Borel space, then there exists a satisfying assignment which is a Borel function. The main tool which we develop for the proof, which is of independent interest, is a parallel version of the Moser-Tardos algorithm which uses the same random bits to resample clauses that are far enough in the dependency graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Moser-Tardos Algorithm with small number of random bits

    math.CO 2022-03 unverdicted novelty 7.0

    Variant of parallel Moser-Tardos algorithm reuses random bits across distant variables in subexponentially growing dependency graphs to achieve constant expected randomness, enabling O(n) deterministic solving and Borel LLL.