近日，计算所关于洛瓦兹局部引理的理论研究成果被第58届计算机科学基础年会（FOCS）录用，这是计算所自1996年来再次在理论计算机顶级会议发表成果。该论文由计算所先进计算机系统研究中心刘兴武副研究员、前瞻实验室何昆博士生与软件所夏盟佶副研究员、ETH王彧弋博士、蚂蚁金服李梁博士合作完成，是一次非常成功的校际合作。

　　此次FOCS录用论文《Variable Version Lova ？sz Local Lemma: Beyond Shearer’s Bound》是关于洛瓦兹局部引理（Lova ？sz Local Lemma，LLL）。该引理是最重要的概率方法之一，在组合数学、理论计算机科学等领域都有很多应用。LLL回答的基本问题是：给定概率空间上一组事件的依赖关系，这些事件的概率满足什么条件，才能保证它们不能覆盖全空间？尽管此问题对抽象版本的LLL已经回答了30多年，但是对于常用的变量版本LLL却知之甚少。本论文从几何角度入手，证明变量版本LLL允许把每个事件标准化为少量方体之并，从而对极限条件找到了充分必要的数学刻画。此外，我们对如下问题提出几乎等价但容易验证的判定条件：什么依赖关系下抽象版本和变量版本LLL的极限概率相同？这些结果有助于深入理解变量版本的洛瓦兹局部引理。

　　FOCS是理论计算机科学领域最顶级的国际会议之一，在整个计算机科学领域享有崇高的声望。FOCS由IEEE计算机学会的计算之数学基础专委会提供资助，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。本年度FOCS在美国马萨诸塞州剑桥市举办，共收到323篇投稿，录用90篇论文，录用率为28%。计算所上一篇FOCS论文于1996年由刘志勇研究员于美国访问期间完成。