近日，中国科学院计算技术研究所关于洛瓦兹局部引理的理论研究成果被第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年由研究员刘志勇于美国访问期间完成。
