姚班计科30班陈立杰同学的研究论文《On the Power of Statistical Zero Knowledge》7月1日被第五十八届IEEE计算机科学基础年会（58th Annual IEEE Symposium on Foundations of Computer Science，FOCS 2017）接收。该论文是陈立杰同学2016年与美国麻省理工学院及雅虎的几位合作者共同完成的，解决了计算复杂性领域的一个重要难题。
零知识证明(zero knowledge proofs systems)在密码学理论和复杂度理论中都有着非常重要的地位。具体来讲，在一个零知识证明系统中，一个证明者要向一个验证者在证明一个命题的正确性的同时，不能让验证者获得除了这个命题的正确性以外的任何信息。 而其中要求最苛刻的被称为统计零知识证明系统(statistical zero knowledge proofs systems，简称SZK)。
访问MIT期间，陈立杰同学发现了指导教师Scott Aaronson教授2010年在STOC会议上发表的研究BQP复杂类（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之间的喻示分割，随后又与合作者一起加强了这个结论。
FOCS是理论计算机领域最顶级的国际学术会议，已连续举办57届，拥有极高的领域影响力，本年度论文接收率约为27.9%。FOCS 2017将于十月在美国加州召开，届时该论文将在大会上以报告形式进行展示。
