姚班本科生國(guó)際計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)上宣講論文

解決計(jì)算復(fù)雜性領(lǐng)域的重要問(wèn)題

清華新聞網(wǎng)10月20日電 姚班計(jì)科30班陳立杰同學(xué)的研究論文《關(guān)于統(tǒng)計(jì)零知識(shí)證明的能力》（On the Power of Statistical Zero Knowledge）于7月1日被第五十八屆國(guó)際電子與電氣工程師協(xié)會(huì)計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)（58th Annual IEEE Symposium on Foundations of Computer Science，F(xiàn)OCS 2017）接收。當(dāng)?shù)貢r(shí)間10月17日，陳立杰赴美國(guó)加州大學(xué)伯克利分校參加年會(huì)并作大會(huì)口頭報(bào)告。陳立杰也成為首位在理論計(jì)算機(jī)科學(xué)領(lǐng)域頂級(jí)會(huì)議計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)上發(fā)文的中國(guó)本科生。

該論文是陳立杰同學(xué)2016年赴美國(guó)麻省理工學(xué)院訪(fǎng)問(wèn)期間，與4名博士研究生及博士后合作完成的，解決了計(jì)算復(fù)雜性領(lǐng)域的一個(gè)重要難題。

零知識(shí)證明(zero knowledge proofs systems)在密碼學(xué)理論和復(fù)雜度理論中都有著非常重要的地位。具體來(lái)講，在一個(gè)零知識(shí)證明系統(tǒng)中，一個(gè)證明者要向一個(gè)驗(yàn)證者在證明一個(gè)命題的正確性的同時(shí)，不能讓驗(yàn)證者獲得除了這個(gè)命題的正確性以外的任何信息。 而其中要求最苛刻的被稱(chēng)為統(tǒng)計(jì)零知識(shí)證明系統(tǒng)(statistical zero knowledge proofs systems，簡(jiǎn)稱(chēng)SZK)。 

統(tǒng)計(jì)零知識(shí)證明原理。

訪(fǎng)問(wèn)美國(guó)麻省理工學(xué)院期間，陳立杰同學(xué)發(fā)現(xiàn)了指導(dǎo)教師斯科特·阿倫森（Scott Aaronson）教授2010年在計(jì)算理論年會(huì)(STOC 2010)會(huì)議上發(fā)表的，研究BQP復(fù)雜類(lèi)（表示量子算法在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算的問(wèn)題的集合）與統(tǒng)計(jì)零知識(shí)證明系統(tǒng)復(fù)雜類(lèi)之間關(guān)系的論文存在漏洞，并寫(xiě)了一篇論文彌補(bǔ)了此漏洞，得到指導(dǎo)教授的高度評(píng)價(jià)。

在指導(dǎo)老師的鼓勵(lì)下，陳立杰與合作者研究了統(tǒng)計(jì)零知識(shí)證明系統(tǒng)和另一個(gè)復(fù)雜度類(lèi)PP的關(guān)系，PP代表多項(xiàng)式時(shí)間內(nèi)可以以嚴(yán)格大于1/2的概率計(jì)算正確的問(wèn)題的集合。該問(wèn)題在2002年由著名量子信息學(xué)者約翰·沃特羅斯（John Watrous）教授提出，在當(dāng)時(shí)斯科特·阿倫森博士構(gòu)造了一個(gè)統(tǒng)計(jì)零知識(shí)證明系統(tǒng)和量子算法在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算的問(wèn)題的集合之間的喻示分割，說(shuō)明了并不存在一個(gè)量子的黑盒算法可以破解統(tǒng)計(jì)零知識(shí)證明系統(tǒng)。在很多情況下，如果將量子力學(xué)的法則稍作修改，就可能得具有更強(qiáng)大的計(jì)算能力的計(jì)算復(fù)雜度類(lèi)，但這些復(fù)雜度類(lèi)基本都包含于PP之中，可見(jiàn)復(fù)雜度類(lèi)PP是量子算法在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算的問(wèn)題的集合的一個(gè)最自然的拓展。陳立杰與合作者在論文中給出了一個(gè)統(tǒng)計(jì)零知識(shí)證明系統(tǒng)和PP的喻示分割(Oracle Separation)，這代表了PP中沒(méi)有一個(gè)黑盒算法(black box algorithm) 可以解決統(tǒng)計(jì)零知識(shí)證明系統(tǒng)中的全部問(wèn)題。換句話(huà)說(shuō)，他們證明即使有比量子計(jì)算（對(duì)應(yīng)BQP）更強(qiáng)計(jì)算能力的計(jì)算機(jī)（對(duì)應(yīng)PP），依然沒(méi)有一種黑盒算法可以解決統(tǒng)計(jì)零知識(shí)證明系統(tǒng)中的所有問(wèn)題。

該研究工作也順帶提出一些新的喻示分割，并且給出了關(guān)于通信復(fù)雜度(Communication Complexity)類(lèi)的結(jié)構(gòu)的一些結(jié)果。陳立杰是論文的主要貢獻(xiàn)者，結(jié)合了之前提出的一些工具，構(gòu)造了統(tǒng)計(jì)零知識(shí)證明系統(tǒng)和PP之間的喻示分割，隨后又與合作者一起加強(qiáng)了這個(gè)結(jié)論。

IEEE計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)是理論計(jì)算機(jī)領(lǐng)域最頂級(jí)的國(guó)際學(xué)術(shù)會(huì)議，已連續(xù)舉辦57屆，擁有極高的領(lǐng)域影響力，本年度論文接收率約為27.9%。姚期智先生創(chuàng)辦的清華學(xué)堂計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班（姚班），矢志踐行“精英教育從本科開(kāi)始”的理念，在國(guó)內(nèi)乃至國(guó)際本科生人才培養(yǎng)項(xiàng)目中保持著領(lǐng)跑優(yōu)勢(shì)。截至目前，從2004級(jí)到2015級(jí)，姚班學(xué)生在本科期間發(fā)表的論文有171篇記錄在冊(cè)，63人次在電氣和電子工程師計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)（FOCS）、計(jì)算理論年會(huì)（STOC）、神經(jīng)信息處理系統(tǒng)大會(huì)（NIPS）、IEEE國(guó)際計(jì)算機(jī)視覺(jué)與模式識(shí)別會(huì)議（CVPR）、國(guó)際人工智能年會(huì)（AAAI）等國(guó)際頂級(jí)會(huì)議上作大會(huì)報(bào)告。

供稿：交叉信息研究院 編輯：華山