姚班本科生国际计算机科学基础年会上宣讲论文
“全球人工智能”拥有十多万AI产业用户，10000多名AI技术专家。主要来自：北大，清华，中科院，麻省理工，卡内基梅隆，斯坦福，哈佛，牛津，剑桥...以及谷歌，腾讯，百度，脸谱，微软，阿里，海康威视，英伟达......等全球名校和名企。
清华新闻网10月20日电 姚班计科30班陈立杰同学的研究论文《关于统计零知识证明的能力》（On the Power of Statistical Zero Knowledge）于7月1日被第五十八届国际电子与电气工程师协会计算机科学基础年会（58th Annual IEEE Symposium on Foundations of Computer Science，FOCS 2017）接收。当地时间10月17日，陈立杰赴美国加州大学伯克利分校参加年会并作大会口头报告。陈立杰也成为首位在理论计算机科学领域顶级会议计算机科学基础年会上发文的中国本科生。
该论文是陈立杰同学2016年赴美国麻省理工学院访问期间，与4名博士研究生及博士后合作完成的，解决了计算复杂性领域的一个重要难题。
零知识证明(zero knowledge proofs systems)在密码学理论和复杂度理论中都有着非常重要的地位。具体来讲，在一个零知识证明系统中，一个证明者要向一个验证者在证明一个命题的正确性的同时，不能让验证者获得除了这个命题的正确性以外的任何信息。 而其中要求最苛刻的被称为统计零知识证明系统(statistical zero knowledge proofs systems，简称SZK)。
统计零知识证明原理。
访问美国麻省理工学院期间，陈立杰同学发现了指导教师斯科特·阿伦森（Scott Aaronson）教授2010年在计算理论年会(STOC 2010)会议上发表的，研究BQP复杂类（表示量子算法在多项式时间内可以计算的问题的集合）与统计零知识证明系统复杂类之间关系的论文存在漏洞，并写了一篇论文弥补了此漏洞，得到指导教授的高度评价。
在指导老师的鼓励下，陈立杰与合作者研究了统计零知识证明系统和另一个复杂度类PP的关系，PP代表多项式时间内可以以严格大于1/2的概率计算正确的问题的集合。该问题在2002年由著名量子信息学者约翰·沃特罗斯（John Watrous）教授提出，在当时斯科特·阿伦森博士构造了一个统计零知识证明系统和量子算法在多项式时间内可以计算的问题的集合之间的喻示分割，说明了并不存在一个量子的黑盒算法可以破解统计零知识证明系统。在很多情况下，如果将量子力学的法则稍作修改，就可能得具有更强大的计算能力的计算复杂度类，但这些复杂度类基本都包含于PP之中，可见复杂度类PP是量子算法在多项式时间内可以计算的问题的集合的一个最自然的拓展。陈立杰与合作者在论文中给出了一个统计零知识证明系统和PP的喻示分割(Oracle Separation)，这代表了PP中没有一个黑盒算法(black box algorithm) 可以解决统计零知识证明系统中的全部问题。换句话说，他们证明即使有比量子计算（对应BQP）更强计算能力的计算机（对应PP），依然没有一种黑盒算法可以解决统计零知识证明系统中的所有问题。
该研究工作也顺带提出一些新的喻示分割，并且给出了关于通信复杂度(Communication Complexity)类的结构的一些结果。陈立杰是论文的主要贡献者，结合了之前提出的一些工具，构造了统计零知识证明系统和PP之间的喻示分割，随后又与合作者一起加强了这个结论。
IEEE计算机科学基础年会是理论计算机领域最顶级的国际学术会议，已连续举办57届，拥有极高的领域影响力，本年度论文接收率约为27.9%。姚期智先生创办的清华学堂计算机科学实验班（姚班），矢志践行“精英教育从本科开始”的理念，在国内乃至国际本科生人才培养项目中保持着领跑优势。截至目前，从2004级到2015级，姚班学生在本科期间发表的论文有171篇记录在册，63人次在电气和电子工程师计算机科学基础年会（FOCS）、计算理论年会（STOC）、神经信息处理系统大会（NIPS）、IEEE国际计算机视觉与模式识别会议（CVPR）、国际人工智能年会（AAAI）等国际顶级会议上作大会报告。（编辑：华山）
系统学习，进入全球人工智能学院
周志华点评AlphaGo Zero：这6大特点非常值得注意！
相关内容
微信扫码咨询专知VIP会员