2017年07月17日 瀏覽次數(shù): 0
姚班計(jì)科30班陳立杰同學(xué)的研究論文《On the Power of Statistical Zero Knowledge》7月1日被第五十八屆IEEE計(jì)算機(jī)科學(xué)基礎(chǔ)年會(huì)(58th Annual IEEE Symposium on Foundations of Computer Science,FOCS 2017)接收。該論文是陳立杰同學(xué)2016年與美國(guó)麻省理工學(xué)院及雅虎的幾位合作者共同完成的,解決了計(jì)算復(fù)雜性領(lǐng)域的一個(gè)重要難題。
零知識(shí)證明(zero knowledge proofs systems)在密碼學(xué)理論和復(fù)雜度理論中都有著非常重要的地位。具體來講,在一個(gè)零知識(shí)證明系統(tǒng)中,一個(gè)證明者要向一個(gè)驗(yàn)證者在證明一個(gè)命題的正確性的同時(shí),不能讓驗(yàn)證者獲得除了這個(gè)命題的正確性以外的任何信息。 而其中要求最苛刻的被稱為統(tǒng)計(jì)零知識(shí)證明系統(tǒng)(statistical zero knowledge proofs systems,簡(jiǎn)稱SZK)。
?????? 訪問MIT期間,陳立杰同學(xué)發(fā)現(xiàn)了指導(dǎo)教師Scott Aaronson教授2010年在STOC會(huì)議上發(fā)表的研究BQP復(fù)雜類(BQP表示量子算法在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算的問題的集合)的論文中,關(guān)于BQP與SZK復(fù)雜類之間關(guān)系的證明存在漏洞,并寫了一篇論文彌補(bǔ)此漏洞,得到指導(dǎo)教授的高度評(píng)價(jià)。
在指導(dǎo)老師的鼓勵(lì)下,陳立杰與合作者研究了SZK和另一個(gè)復(fù)雜度類PP的關(guān)系,PP代表多項(xiàng)式時(shí)間內(nèi)可以以嚴(yán)格大于1/2的概率計(jì)算正確的問題的集合。該問題在2002年由著名量子信息學(xué)者John Watrous教授提出,在當(dāng)時(shí)Scott Aaronson博士構(gòu)造了一個(gè)SZK和BQP之間的喻示分割,說明了并不存在一個(gè)量子的黑盒算法可以破解SZK。在很多情況下,如果將量子力學(xué)的法則稍作修改,就可能得具有更強(qiáng)大的計(jì)算能力的計(jì)算復(fù)雜度類,但這些復(fù)雜度類基本都包含于PP之中,可見復(fù)雜度類PP是BQP的一個(gè)最自然的拓展。陳立杰與合作者在論文中給出了一個(gè)SZK和PP的喻示分割(Oracle Separation),這代表了PP中沒有一個(gè)黑盒算法(black box algorithm) 可以解決SZK中的全部問題。換句話說,他們證明哪怕有比量子計(jì)算(對(duì)應(yīng)BQP)更強(qiáng)計(jì)算能力的計(jì)算機(jī)(對(duì)應(yīng)PP),依然沒有黑盒算法可以解決SZK中的所有問題。
該研究工作也順帶提出一些新的喻示分割,并且給出了關(guān)于通信復(fù)雜度(Communication Complexity)類的結(jié)構(gòu)的一些結(jié)果。陳立杰是論文的主要貢獻(xiàn)者之一,結(jié)合了之前提出的一些工具,構(gòu)造了SZK和PP之間的喻示分割,隨后又與合作者一起加強(qiáng)了這個(gè)結(jié)論。
FOCS是理論計(jì)算機(jī)領(lǐng)域最頂級(jí)的國(guó)際學(xué)術(shù)會(huì)議,已連續(xù)舉辦57屆,擁有極高的領(lǐng)域影響力,本年度論文接收率約為27.9%。FOCS 2017將于十月在美國(guó)加州召開,屆時(shí)該論文將在大會(huì)上以報(bào)告形式進(jìn)行展示。
版權(quán)與免責(zé)聲明:本網(wǎng)頁(yè)的內(nèi)容由收集互聯(lián)網(wǎng)上公開發(fā)布的信息整理獲得。目的在于傳遞信息及分享,并不意味著贊同其觀點(diǎn)或證實(shí)其真實(shí)性,也不構(gòu)成其他建議。僅提供交流平臺(tái),不為其版權(quán)負(fù)責(zé)。如涉及侵權(quán),請(qǐng)聯(lián)系我們及時(shí)修改或刪除。郵箱:sales@allpeptide.com