New versions of Lovasz Local Lemma and their applications

CategoryPublications 248

Authors: Kun He, Xiaoming Sun

Published in: SCIENCE CHINA Information Sciences (SCIS 2020)

Date of Publication: Oct 19, 2020


Lovász Local Lemma (LLL) is an important tool in combinatoricsand probability theory to show the existence of combinatorial objects meeting a collection of criteria if these criteria are “weakly dependent”.It was first proposed by ErdHos and Lovász in 1975.Since then, many applications of LLL have been found in combinatorics, theoretic computer science and physics.Recently, several new versions of LLL have been proposed.Especially, the big breakthrough in the constructive LLL has attracted lots of attention in theoretical computer science.In this paper, we will review the recent progress in the research of LLL, including the new versions of LLL and their applications.We will give the tight bounds of the abstract LLL, lopsided LLL, variable LLL and quantum LLL.We will also provide the connection between the abstract LLL and statistical physics and that between the quantum LLL and quantum physics.The LLL can be used to prove the existence of solutions, find a solution efficiently, count the number of solutions and sample a solution uniformly at random.We will also illustrate these applications of LLL with the SAT problem and the quantum SAT problem.

View Full Text

Keywords2020Big data analytics under constrained resourcesKun HeSCIS Previous: Next: