新智元引荐
来历：会议之眼
【新智元导读】2019顶会上，深度学习大神、亚马逊AI主任科学家李沐此前就是FOCS获奖者，而MIT博士生、清华姚班毕业生陈立杰本年一连中奖3篇，并荣获最佳学生论文奖。来新智元 AI 朋友圈与AI大咖一同评论吧～
会议之眼A类、CCF A类会议FOCS（Foundations of Computer Science）是由IEEE核算机协会核算数学根底技能委员会主办的世界顶会！大会致力于为核算机理论的根底研讨和新方法创始范畴的研讨者供给一个沟通和展现的渠道。其高逼格、难搞定的程度让不少科研作业者只得仰视。深度学习大神、亚马逊AI主任科学家李沐此前就是FOCS获奖者，而MIT博士生、清华姚班毕业生陈立杰本年一连中奖3篇，并荣获最佳学生论文奖。
FOCS每年举行一次，第60届核算机科学根底IEEE研讨会定于2019年11月9日至12日在美国马里兰州最大城市巴尔的摩举行。论文提交截止日期为同年4月5日，接纳发布日期为7月1日。小程序会议之眼plus供给了会议时刻、地址、等级和官网查询地址。致力于在核算机根底理论研讨范畴发Paper的小伙伴要早做规划，及时保藏呀！
最佳论文
Lower bounds for maximal matchings andmaximal independent sets
Alkida Balliu,Sebastian Brandt,JuhoHirvonen,Dennis Olivetti,Mika l Rabie, Jukka Suomela
论文简介：
在O（Δ+ log n）的通讯回合中，存在用于找到最大匹配和最大独立集的分布式图形算法。这儿n是节点数，Δ是最大度。Linial的下限标明对n的依靠是最优的：即便Δ= 2，这样一些问题也无法在O（Δ+ log n）轮中处理。可是，对Δ的依靠性是一个长期存在的悬而未决的问题，现在在上下限之间存在指数距离。
作者证明上限是严密的。在分布式核算的本地模型中，运用任何随机算法都无法在O（Δ+ loglogn / logloglogn）次序中找到最大匹配和最大独立集。因而，没有一个确认的算法能够在O（Δ+ logn / loglogn）次序中运转最大匹配或最大独立集。这可当作n的函数对从前的下限进行改善。
NEEXP MIP*
Authors: AnandNatarajan,John Wright
论文简介：
作者研讨了multiprover交互式证明体系。证明了经典的multiprover交互证明体系的效果，其首要结果是等式MIP = NEXP。事实证明，量子多重证明者交互式证明体系的功用难以证明，其间证明者能够同享羁绊。Ito和Vidick曾提出了MIP *的最著名下限是NEXP。至于上限，MIP *能够和RE相同大。
这项作业的首要结果是在提出了MIP *的NEEXP（不确认的双指数时刻）。这是对从前下限的一个指数改善，标明具有羁绊证明者的证明体系至少比经典证明者在指数上具有更大的功用。在作者的协议中，验证者将经典的NEEXP，指数上的MIP协议委派给两个羁绊证明者：证明者经过丈量其同享状况来取得其指数问题，并运用经典PCP来证明其答案的正确性。至关重要的是协议的稳健性，每个参与者不只应该正确地对自己的问题进行抽样，并且还应防止会走漏其他参与者的抽样问题的状况呈现。
Automating Resolution is NP-Hard
Albert Atserias,Moritz Müller
论文简介：
作者发现批驳处理的问题在于非确认性多项式复杂度的归约问题。在证明复杂性方面，除非P = NP，不然处理方案无法主动履行。区别具有多项式长度的分辨率辩驳的公式和不具有次指数长度辩驳的公式对错确认性多项式复杂度的归约问题。这也意味着，除非在SUBEXP或QP中别离包括NP，不然分辨率无法在指数以下的时刻或准多项式时刻内主动履行。
最佳学生论文
EfficientConstruction of Rigid Matrices Using an NP Oracle
Josh Alman, Lijie Chen
Faster Minimum k-cut of a Simple Graph
Jason Li
小帮手现已打包收拾好上述文章，重视核算机科学根底研讨的朋友们快快保藏起来!阅览顶会最佳论文，重视最新动态！
