佳能打印機(jī)mp259(佳能打印機(jī)ip2780)

前沿拓展：

編輯：Joey 好困

【新智元導(dǎo)讀】2022年計算機(jī)理論頂會STOC正式開幕，來自清華姚班的三位00后學(xué)霸斬獲最佳學(xué)生論文獎。

近日，理論計算機(jī)科學(xué)領(lǐng)域頂級國際會議第54屆ACM計算理論年會（STOC 2022）拉開帷幕。

清華姚班的三位00后學(xué)霸范致遠(yuǎn)、李嘉圖與楊天祺，憑借著「偽隨機(jī)函數(shù)的精確復(fù)雜性與計算復(fù)雜性理論中自舉現(xiàn)象的黑盒自然證明障礙」奪得最佳學(xué)生論文獎。

從左至右分別為范致遠(yuǎn)、李嘉圖和楊天祺（來源：**科學(xué)報）

ACM計算理論年會（STOC）是理論計算機(jī)科學(xué)領(lǐng)域最頂級的國際會議，在整個計算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，并被公認(rèn)屬于難度最高的會議之一。它與IEEE計算機(jī)科學(xué)基礎(chǔ)年度研討會（FOCS）并稱理論計算機(jī)科學(xué)兩大頂會。

STOC由ACM SIGACT（Special Interest Group in Algorithms and Computation Theory）主辦，涵蓋的領(lǐng)域包括算法和數(shù)據(jù)結(jié)構(gòu)、計算復(fù)雜性、密碼學(xué)、計算幾何、組合學(xué)、隨機(jī)與去隨機(jī)化、算法博弈論和量子計算等。

2022年的STOC共收到457篇投稿，錄用135篇，接收率約為29%。第二再從中評選出2篇最佳論文獎，以及2篇最佳學(xué)生論文獎。這么算下來的話，獲獎率僅為2.9%。

獲得最佳論文獎的2篇論文，分別來自魏茨曼科學(xué)研究所、希伯來大學(xué)，以及莫斯科國立大學(xué)。

獲得最佳學(xué)生論文獎的2篇論文，分別來自麻省理工學(xué)院、微軟研究院，以及清華大學(xué)。

演講地址：https://www.**.com/watch?v=QcBypyG6oMU

6月23日，正是這三人獲獎?wù)撐牡膮R報時間。

論文地址：https://dl.acm.org/doi/abs/10.1145/3519935.3520010

偽隨機(jī)函數(shù)(pseudorandom functions)是無法與隨機(jī)函數(shù)區(qū)分開的函數(shù)族。它作為密碼學(xué)許多構(gòu)造的起點，是密碼學(xué)的基礎(chǔ)。因此構(gòu)造高效的偽隨機(jī)函數(shù)在理論及應(yīng)用中有多種意義。

論文研究了偽隨機(jī)函數(shù)的電路復(fù)雜性，在多個重要的電路復(fù)雜性類中對偽隨機(jī)函數(shù)給出了緊的上界與下界。例如證明了在一般電路中，若多項式大小的電路可計算的偽隨機(jī)函數(shù)存在，則存在一個僅需大約2n個門的電路族即可計算的偽隨機(jī)函數(shù)。同時，該研究無條件地證明了計算任何偽隨機(jī)函數(shù)至少需要2n-2個門。

范致遠(yuǎn)

2017年7月30日，范致遠(yuǎn)在第34屆全國青少年信息學(xué)奧林匹克競賽中拿到金牌，清華大學(xué)也向他拋來了「橄欖枝」。

范致遠(yuǎn)成功獲得了清華大學(xué)化學(xué)生物基礎(chǔ)科學(xué)班一本線錄取資格。

來看看大神滿滿的獲獎經(jīng)歷。

再看看范致遠(yuǎn)曾經(jīng)就讀的杭州學(xué)軍中學(xué)，兩次獲世界冠軍，獲國際金牌3枚，亞太地區(qū)金牌29枚、全國金牌23枚，全國聯(lián)賽一等獎259人次。

近十年來，錄取清北人數(shù)達(dá)七八十人，其學(xué)生遍布哈佛、麻省理工、斯坦福等國際名校，就職于谷歌、Facebook、微軟、百度等著名IT企業(yè)。

說成「清北的搖籃」也不過分。

李嘉圖

李嘉圖高中就讀于太原五中，18年7月，李嘉圖同學(xué)在第35屆全國青少年信息學(xué)奧林匹克競賽中斬獲金牌，進(jìn)入國家集訓(xùn)隊，同時獲得保送清華大學(xué)資格。

2018年1月29日至2月1日舉辦的「清華大學(xué)全國優(yōu)秀中學(xué)生信息學(xué)冬季體驗營」中，清華大學(xué)計算機(jī)系面向全國知名高中邀請了「213名優(yōu)秀信息學(xué)奧賽學(xué)生」參加體驗營。

李嘉圖是山西省唯一一位獲邀參加體驗營的同學(xué)。

楊天祺

高中就讀于南京師范大學(xué)附屬中學(xué)，曾獲2018年全國青少年信息學(xué)奧林匹克聯(lián)賽（省級賽區(qū)）一等獎、2018年全國青少年信息學(xué)奧林匹克競賽一等獎。

2019年入選信息學(xué)國家集訓(xùn)隊，并獲得清華保送資格。研究興趣是計算復(fù)雜性，目前專注于電路下限。

那么這樣三位來自全國各地的天才少年，是怎樣組建團(tuán)隊并成功奪得最佳學(xué)生論文的呢？

事實上，這篇論文從一開始的構(gòu)思，到研究團(tuán)隊的組建再到成功發(fā)表獲獎，其過程并不是一帆風(fēng)順。

在《**科學(xué)報》的一篇采訪中，李嘉圖表示，他們?nèi)瞬⒎且婚_始就在一個團(tuán)隊。

這篇論文最初的理念雛形由李嘉圖和楊天祺二人提出。

大一下學(xué)期開始，他們在姚期智院士講授的計算機(jī)應(yīng)用數(shù)學(xué)課程中收獲頗豐，并提前選修了段然老師的計算理論課程。這門課程，讓他了解到計算復(fù)雜性領(lǐng)域還有許多值得深耕的領(lǐng)域。

那段時間里，他們一起翻看了近些年電路復(fù)雜性理論的一個重要突破，即麻省理工學(xué)院教授Ryan Williams提出的，證明電路復(fù)雜度下界（circuit lower bound）的算法方法（algorithmic approach）。

李嘉圖說，「我們想要從一個電路復(fù)雜度理論的前沿問題入手，了解這個領(lǐng)域的背景、主要技術(shù)，以及目前的重要問題」。

不過，實際進(jìn)展并沒有想象那么輕松。經(jīng)過對該領(lǐng)域的一番研究后，二人雖然大致明白了這一理論的框架，但并未發(fā)現(xiàn)值得他們研究的選題。

這時范致遠(yuǎn)的加入，如「及時雨」一般，為后續(xù)研究指出了一個大概的方向。

范致遠(yuǎn)說，「我們?nèi)齻€人的合作氛圍很舒服，大家經(jīng)常交流和探討，思想會碰撞出很多火花。后來，我們對原方法進(jìn)行了大幅度的簡化和改進(jìn)，而且用完全不同的技術(shù)探索了這一問題的更多側(cè)面」。

范致遠(yuǎn)的加入為團(tuán)隊的研究進(jìn)展提供了全新的動力，相關(guān)研究成果也緊接著噴涌而出。

在論文的終稿里，最初預(yù)設(shè)的問題已經(jīng)不是最終的結(jié)果，最后論文的展示也取得成功，即在三個模型中證明了上下界。

值得一提的是，李嘉圖和楊天祺的另一篇論文也被STOC 2022接收了。

論文地址：https://dl.acm.org/doi/10.1145/3519935.3519976

演講地址：https://www.**.com/watch?v=54ILPK6JK5c

電路復(fù)雜性（circuit complexity）是復(fù)雜性理論中廣為關(guān)注的問題。其中一個經(jīng)典結(jié)論是大多數(shù)語言都需要指數(shù)級大小的電路才足以進(jìn)行判定，但是該結(jié)論的證明是非構(gòu)造性的。給出一個需要很大的電路才能判定的具體語言是有幾十年歷史的開放問題。

在此之前，最好的結(jié)果是Find, Golovnev, Hirsch, and Kulikov于2016年給出的：存在一個多項式可計算的語言不能被(3+1/86)n-o(n)大小的電路計算。該研究改進(jìn)了他們的方法，證明了同一個語言不能被3.1n-o(n)大小的電路計算。