Simple Local Computation Algorithms for the General Lovasz Local Lemma

2018/09/21 by Achlioptas, Dimitris, Gouleakis, Themis, Iliopoulos, Fotis
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1809.07910

Abstract

We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lovász Local Lemma (LLL). LCA is a class of sublinear algorithms proposed by Rubinfeld et al.~\citeRonitt that have received a lot of attention in recent years. The LLL is an existential, sufficient condition for a collection of sets to have non-empty intersection (in applications, often, each set comprises all objects having a certain property). The ground-breaking algorithm of Moser and Tardos~\citeMT made the LLL fully constructive, following earlier results by Beck~\citebeck_lll and Alon~\citealon_lll giving algorithms under significantly stronger LLL-like conditions. LCAs under those stronger conditions were given in~\citeRonitt, where it was asked if the Moser-Tardos algorithm can be used to design LCAs under the standard LLL condition. The main contribution of this paper is to answer this question affirmatively. In fact, our techniques yield LCAs for settings beyond the standard LLL condition.

Related

• A constructive proof of the general Lovasz Local Lemma
• Extensions of the Algorithmic Lovasz Local Lemma
• A new notion of commutativity for the algorithmic Lovász Local Lemma
• Infinite computable version of Lovasz Local Lemma
• Deterministic Algorithms for the Lovasz Local Lemma