论文标题
对于算法Lovász本地引理的新的通勤概念
A new notion of commutativity for the algorithmic Lovász Local Lemma
论文作者
论文摘要
Lovász局部引理（LLL）是概率组合学的强大工具，可用于确定满足某些属性的对象的存在。 Moser和Tardos和后续作品的突破性论文表明，LLL与一类随机局部搜索算法有着密切的联系，用于查找此类理想的对象。特别是，它可以看作是这种类型的算法快速收敛的足够条件。 除了存在和快速收敛到理想对象的条件外，人们可能自然会提出有关这些算法属性的进一步问题。例如，“它们可以并行吗？”，“它们可以输出多少个解决方案？”，“解决方案的预期“权重”是什么？在本文中，我们介绍了一种新的，非常自然的，更一般的通勤性概念（本质上是矩阵的通勤性），该概念使我们能够显示出具有更简单的证据的LLL启发的本地搜索算法的许多新的精制属性。
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.
