Borel version of the Local Lemma
Borel version of the Local Lemma
复制标题
局部引理的 Borel 版本
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
K. Tyros
中科院分区：
文献类型：
--
作者：
Endre Cs'oka;L. Grabowski;A. M'ath'e;O. Pikhurko;K. Tyros
我们证明了局部引理的一个博雷尔（Borel）版本，即我们表明，在适当的假设下，如果局部引理中的变量集具有博雷尔空间的结构，那么存在一个是博雷尔函数的满足赋值。我们为证明所开发的主要工具（它本身具有独立的研究价值）是莫泽 - 塔尔多斯（Moser - Tardos）算法的一个并行版本，该版本使用相同的随机比特对依赖图中距离足够远的子句进行重新采样。
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.