清華新聞網(wǎng)5月17日電 近日，計(jì)算機(jī)科學(xué)領(lǐng)域頂級(jí)國(guó)際會(huì)議第54屆ACM計(jì)算理論年會(huì)（STOC 2022 54th Annual Symposium on the Theory of Computing）官網(wǎng)公布，清華大學(xué)交叉信息研究院師生及校友共有7篇論文被接收，其中計(jì)科班（簡(jiǎn)稱(chēng)“姚班”）91班范致遠(yuǎn)、計(jì)科92班李嘉圖與楊天祺三位同學(xué)共同完成的論文“偽隨機(jī)函數(shù)的精確復(fù)雜性與計(jì)算復(fù)雜性理論中自舉現(xiàn)象的黑盒自然證明障礙”（The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity）被大會(huì)接收，并獲評(píng)最佳學(xué)生論文。
偽隨機(jī)函數(shù)（pseudorandom functions）是無(wú)法與隨機(jī)函數(shù)區(qū)分開(kāi)的函數(shù)族。它作為密碼學(xué)許多構(gòu)造的起點(diǎn)，是密碼學(xué)的基礎(chǔ)。因此構(gòu)造高效的偽隨機(jī)函數(shù)在理論及應(yīng)用中有多種意義。該論文研究了偽隨機(jī)函數(shù)的電路復(fù)雜性，在多個(gè)重要的電路復(fù)雜性類(lèi)中對(duì)偽隨機(jī)函數(shù)給出了緊的上界與下界。例如證明了在一般電路中，若多項(xiàng)式大小的電路可計(jì)算的偽隨機(jī)函數(shù)存在，則存在一個(gè)僅需大約2n個(gè)門(mén)的電路族即可計(jì)算的偽隨機(jī)函數(shù)。同時(shí)，該研究無(wú)條件地證明了計(jì)算任何偽隨機(jī)函數(shù)至少需要2n-2個(gè)門(mén)。
論文插圖：兩層線(xiàn)性閾門(mén)電路
這些上下界結(jié)果為電路復(fù)雜性理論提供了新的理解，也解釋了為何一些廣為相信的猜想難以被證明。特別地，針對(duì)目前電路復(fù)雜性理論中存在的“自舉現(xiàn)象”（bootstrapping phenomena），該研究指出，要想從這些現(xiàn)象推出P vs NP等重要開(kāi)放問(wèn)題的答案，還需要一些全新的證明思路。
ACM計(jì)算理論年會(huì)（STOC）是理論計(jì)算機(jī)科學(xué)領(lǐng)域最頂級(jí)的國(guó)際會(huì)議，在整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，并被公認(rèn)是難度最高的會(huì)議之一。STOC2022將于意大利羅馬召開(kāi)，本次會(huì)議共接收論文投稿457篇，錄用135篇，接收率約為29%。
供稿：交叉信息研究院
編輯：陳曉艷
審核：周襄楠
