看国产毛毛片的网站,国产免费一区不卡在线,www. 久色

前沿拓展：

編輯：Joey 好困

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

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

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

從左至右分別為范致遠、李嘉圖和楊天祺（來源：**科學報）

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

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

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

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

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

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

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

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

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

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

范致遠

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

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

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

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

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

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

李嘉圖

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

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

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

楊天祺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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