洛瓦兹局部引理是组合数学和概率论中的重要工具。近年来局部引理领域取得了很多新进展，这些新进展带来了理论计算机中很多开放问题的重大突破。其中，Moser和Tardos关于构造版本局部引理的工作获得了2020年的哥德尔奖。.本项目拟围绕构造版本局部引理领域最核心的开放问题展开研究。理论方面，结合变量版本局部引理，证明本领域最重要的猜想，即在变量模型下存在构造算法在Shearer界之外依然快速收敛。同时，刻画构造算法选取事件和变量的规则对收敛条件的影响。应用方面，利用构造版本局部引理改进一些重要的计数和采样问题的界。我们首先给出了变量和量子版本局部引理紧的条件，并利用构造版本局部引理刻画了一类采样算法的精确期望时间。这些成果直接和本项目的研究相关。本项目研究成果可望解决构造版本局部引理领域的核心难题，提出更强的构造版本局部引理，从而为理论计算机领域提供强有力的工具。因此，具有重要的科学意义。

Lovasz Local Lemma (LLL) is a power tool in combinatorics and probability theory, and it is also one of the most important probabilistic methods. In recent years, many new developments have been achieved in the field of LLL. These developments led to many breakthroughs in theoretical computer science. Specifically, Moser and Tardos proposed a new constructed LLL under the variable model. The work won the Gödel Award in 2020...In this project, we will study the key problems about the constructive LLL. Theoretically, the most important conjecture about LLL is that there exists a constructive algorithm which still converges quickly outside Shearer’s bound under the variable model. We plan to prove this conjecture based on the new results of variable LLL. Meanwhile, the constructive algorithms take different rules for selecting bad events and variables. We will also depict how these rules affect the convergence conditions. In terms of application, the constructive LLL has many applications in counting and sampling. We plan to improve the bounds of some important problems in this filed. We first prove the tight bounds of the variable LLL and quantum LLL. We also prove the tight bound of the expected time of a class of sampling algorithms with the tools in the filed of constructive LLL. These results are closely related to the research of this project. Through the research of this project, we expect to solve the key problems in the field of constructive LLL and prove a stronger constructive LLL, which will be a powerful tool in theoretical computer science. Thus, this project is of great scientific value.