姚班本科生FOCS宣讲论文 解决计算复杂性领域的著名问题

姚班计科30班陈立杰同学的研究论文《On the Power of Statistical Zero Knowledge》7月1日被第五十八届IEEE计算机科学基础年会（58th Annual IEEE Symposium on Foundations of Computer Science，FOCS 2017）接收。该论文是陈立杰同学2016年赴美国麻省理工学院访问期间，与4名博士研究生及博士后合作完成的，解决了计算复杂性领域的一个重要难题。当地时间10月17日，陈立杰赴美国加州大学伯克利分校参加FOCS 2017并作大会口头报告。陈立杰也成为首位在理论计算机科学领域顶级会议FOCS上发文的中国本科生。

零知识证明(zero knowledge proofs systems)在密码学理论和复杂度理论中都有着非常重要的地位。具体来讲，在一个零知识证明系统中，一个证明者要向一个验证者在证明一个命题的正确性的同时，不能让验证者获得除了这个命题的正确性以外的任何信息。 而其中要求最苛刻的被称为统计零知识证明系统(statistical zero knowledge proofs systems，简称SZK)。

访问MIT期间，陈立杰同学发现了指导教师Scott Aaronson教授2010年在STOC会议上发表的，研究BQP复杂类（BQP表示量子算法在多项式时间内可以计算的问题的集合）与SZK复杂类之间关系的论文存在漏洞，并写了一篇论文弥补了此漏洞，得到指导教授的高度评价。

在指导老师的鼓励下，陈立杰与合作者研究了SZK和另一个复杂度类PP的关系，PP代表多项式时间内可以以严格大于1/2的概率计算正确的问题的集合。该问题在2002年由著名量子信息学者John Watrous教授提出，在当时Scott Aaronson博士构造了一个SZK和BQP之间的喻示分割，说明了并不存在一个量子的黑盒算法可以破解SZK。在很多情况下，如果将量子力学的法则稍作修改，就可能得具有更强大的计算能力的计算复杂度类，但这些复杂度类基本都包含于PP之中，可见复杂度类PP是BQP的一个最自然的拓展。陈立杰与合作者在论文中给出了一个SZK和PP的喻示分割(Oracle Separation)，这代表了PP中没有一个黑盒算法(black box algorithm) 可以解决SZK中的全部问题。换句话说，他们证明哪怕有比量子计算（对应BQP）更强计算能力的计算机（对应PP），依然没有黑盒算法可以解决SZK中的所有问题。

该研究工作也顺带提出一些新的喻示分割，并且给出了关于通信复杂度(Communication Complexity)类的结构的一些结果。陈立杰是论文的主要贡献者，结合了之前提出的一些工具，构造了SZK和PP之间的喻示分割，随后又与合作者一起加强了这个结论。