Borel version of the Local Lemma
From MaRDI portal
Publication:6503229
arXiv1605.04877MaRDI QIDQ6503229FDOQ6503229
Authors: Endre Csóka, Łukasz Grabowski, András Máthé, Oleg Pikhurko, Konstantinos Tyros 
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 page was built for publication: Borel version of the Local Lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6503229)
