邮箱登录 | 所务办公 | 收藏本站 | English | 中国科学院
 
首页 计算所概况 新闻动态 科研成果 研究队伍 国际交流 技术转移 研究生教育 学术出版物 党群园地 科学传播 信息公开
新闻动态
计算所新闻
媒体文摘
现在位置:首页 > 新闻动态 > 计算所新闻
顶级会议FOCS论文录用,计算所理论研究取得进展
2017-07-18 | 【 【打印】【关闭】

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

 
网站地图 | 联系我们 | 意见反馈 | 所长信箱
 
京ICP备05002829号 京公网安备1101080060号