北大圖靈班本科生獲STOC最佳論文獎！這個對標(biāo)清華姚班的人才計劃，正在頻頻交出答卷

魚羊 乾明 2020-06-25 12:41:39 來源：量子位

乾明 魚羊 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI

ACM計算理論年會（STOC）正在線上舉辦中。

最新消息，一位江蘇常州的小哥哥一口氣中了2篇論文，還拿下了最佳論文獎。

而且他還是名本科生，首位拿下STOC最佳論文獎的中國本科生。

沒錯，就是那個理論計算機(jī)領(lǐng)域頂級會議，難度和含金量都穩(wěn)居第一梯隊(duì)的STOC。

他叫吳克文，畢業(yè)于江蘇省常州高級中學(xué)，2016年被北京大學(xué)錄取，2017年成為北大圖靈班首屆學(xué)生，現(xiàn)在即將成為北大圖靈班首屆畢業(yè)生。

北大圖靈班，這個致力于為中國培養(yǎng)計算機(jī)科學(xué)界下一代領(lǐng)軍人物的國際化人才培養(yǎng)計劃，今年開始交出了自己“答卷”：

同樣的優(yōu)秀，一點(diǎn)不輸隔壁的姚班。

北大學(xué)霸斬獲STOC最佳論文獎

STOC是個什么樣的會議？

作為中國計算機(jī)學(xué)會（CCF）推薦的計算機(jī)科學(xué)理論方向A類會議，STOC和FOCS這樣的頂會，也被公認(rèn)為是計算機(jī)科學(xué)領(lǐng)域難度最大、含金量最高的會議。

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

在STOC 2020中，吳克文有兩篇論文發(fā)表。

其中，與普林斯頓大學(xué)Ryan Alweiss、UCSD副教授Shachar Lovett，以及哈佛大學(xué)博士后Jiapeng Zhang合作的《太陽花引理的改進(jìn)（Improved bounds for the sunflower lemma）》，獲得STOC 2020最佳論文獎。

△論文畫風(fēng)長這樣

太陽花（sunflower）是一種常見的組合結(jié)構(gòu)，它表示若干兩兩相交均相同的集合。

1960年，數(shù)學(xué)家Paul Erd?s和Richard Rado提出了太陽花猜想。

這一猜想有關(guān)于物體的幾何。以xy平面上的點(diǎn)的集合為例，首先需要確定的是在每個集合中包含的點(diǎn)的固定數(shù)量，然后開始隨機(jī)畫環(huán)，讓每個環(huán)，或者說每個集合都含有這一數(shù)量的點(diǎn)。環(huán)與環(huán)可以重疊，所以有的點(diǎn)可能會屬于不止一個集合中。

△圖源：QuantumMagazine

Erd?s和Rado提出的猜想是，當(dāng)繪制足夠多的環(huán)時，一定會形成太陽花，要么作為不相交集出現(xiàn)，要么作為集合以正確的方式重疊的形式出現(xiàn)。

其后，他們證明了，這個“足夠多”的量級是w^w。

也就是說，對包含100個點(diǎn)的集合來說，要確保能找到一個由3個集合組成的太陽花，需要100^100個集合。

但數(shù)學(xué)家們當(dāng)時就推測，實(shí)際需要的集合數(shù)一定比w^w小得多，應(yīng)該是O(1)^w。

但在之后的近60年時間中，后續(xù)的研究都沒能突破w^w這個量級。

而這篇STOC 2020最佳論文，就是在這一問題上實(shí)現(xiàn)了重大的突破——將約束改進(jìn)為約 (log w)^w。

也就是說，將原來的結(jié)果改善了一個數(shù)量級！

在這項(xiàng)研究中，吳克文和他的合作者們將問題分解為兩種不同的場景：

第一種場景較為簡單，即集合存在大量重疊的情況。

研究人員首先要確定的是，在這個系統(tǒng)中，是否存在一組在很大一部分集合中是共有的點(diǎn)。

一旦確定了這樣一組點(diǎn)，他們就可以把對太陽花的搜索限制在包含這組點(diǎn)的那部分集合中。通過這種方式不斷修剪，直到找到太陽花為止。

第二種場景則更為困難。研究人員需要分析的是當(dāng)集合沒有太多重疊時會發(fā)生什么。在這種情況下，最有可能產(chǎn)生太陽花的方法是設(shè)置三個不相交的集合。

其中的難點(diǎn)在于，要證明三個完全獨(dú)立的集合隱藏在大量輕度重疊的集合中并非易事。

于是，研究人員將布爾函數(shù)運(yùn)用到了這個問題中，

首先，為特定集合中的每個點(diǎn)分配一個標(biāo)簽：如果它只包含在一個集合中，則為1；否則，設(shè)為0。

如果每個輸入點(diǎn)都是1，那么布爾函數(shù)將輸出1 （真），就意味著集合中的每個點(diǎn)都只在那個集合中，即集合不相交。因此，一個為“真”的結(jié)果表明存在找到太陽花的正確條件。

通過嚴(yán)格證明這種對應(yīng)關(guān)系，這篇論文證明了，(log w)^w個集合，足以確保太陽花的產(chǎn)生。

由于太陽花結(jié)構(gòu)的普遍性，該引理在計算機(jī)科學(xué)與組合數(shù)學(xué)中都有很多應(yīng)用。

另一篇論文，同樣是吳克文和Shachar Lovett、Jiapeng Zhang合作的成果，《利用隨機(jī)賦值的決策表壓縮（Decision list compression by mild random restrictions）》。

決策表（decision list）是一種常見的布爾函數(shù)，它可以簡便地寫為 if-else 嵌套代碼段。

決策表壓縮的結(jié)果表明，給定一個任意長的 if-else 代碼段，如果每個 if 中依賴的變量都不太多，那么就可以用一個“長度可控”的 if-else 代碼段來近似它，且每個 if 中依賴的變量依然不多。

在這篇論文中，研究人員對“長度可控”證明了漸進(jìn)意義上緊的界，并證實(shí)了2013年由 Gopalan, Meka, Reingold 提出的析取范式壓縮的猜想，同時提供了若干在布爾函數(shù)分析、學(xué)習(xí)理論中的應(yīng)用。

據(jù)北大前沿計算研究中心消息，作為圖靈班第一屆畢業(yè)生，接下來，吳克文將前往UC伯克利繼續(xù)深造。

北大圖靈班交答卷：創(chuàng)辦三年，迎來首屆畢業(yè)生

作為首屆畢業(yè)生，吳克文的最新成果，毫無疑問展現(xiàn)出了北大圖靈班的實(shí)力。

北大圖靈班正式創(chuàng)辦于2017年，定位是“為中國培養(yǎng)計算機(jī)科學(xué)界下一代領(lǐng)軍人物的國際化人才”，對標(biāo)“清華姚班”的意味再明顯不過。

領(lǐng)銜者也是一位圖靈獎得主——計算機(jī)科學(xué)領(lǐng)域大師約翰·霍普克羅夫特（John Hopcroft），2017年5加入北京大學(xué)信息科學(xué)技術(shù)學(xué)院，擔(dān)任圖靈班指導(dǎo)委員會主任。

在培養(yǎng)方案上，同樣注重多學(xué)科交叉、科研實(shí)踐和國際交流。吳克文同學(xué)的最新研究成果，正是其在海外交流時完成的。

與姚班不同的是，圖靈班的學(xué)生并不是在高考時選拔，而是每年從大一的學(xué)生中選拔，雖然基礎(chǔ)要求不高（2018年要求）：

1.成績優(yōu)良，已修課程績點(diǎn)≥3.0。

2.已修數(shù)學(xué)A類課程（《數(shù)學(xué)分析I》和《高等代數(shù)I》）成績≥80分，且《計算概論A》成績 ≥85分；本學(xué)期在修《數(shù)學(xué)分析II》和《高等代數(shù)II》。

3.非信息科學(xué)技術(shù)學(xué)院的學(xué)生報名，須在校內(nèi)門戶提交轉(zhuǎn)院（系）轉(zhuǎn)專業(yè)申請。

但想要進(jìn)入其中并不容易——其每年只招收不超過30人。

2018年，北大圖靈班在原有計算機(jī)科學(xué)方向基礎(chǔ)上，新增了人工智能方向，每個方向招收30人，總共不過60人。

與姚班相同的是，北大圖靈班一樣人才輩出：吳克文是其中代表，但不僅僅只有吳克文。

• 2018年，2016級本科生曹芃、許逸倫同學(xué)（大三）共同一作的論文被ICLR 2019接收。
• 2019年，許逸倫、曹芃共同一作的論文被NeurIPS 2019接收。
• 2019年，2016級吳潤迪共同一作論文被SIGGRAPH 2019接收。
• 2020年，許逸倫和斯坦福研究學(xué)者合作的論文，以滿分被ICLR 2020選為口頭展示論文 (oral)。
• 2020年，2017級本科生李沛卓共同一作的論文，被SIGGRAPH 2020接收。

現(xiàn)在，圖靈班迎來了首批畢業(yè)生，從他們頻頻透露出成果來看，這個答卷足夠優(yōu)秀。

北大圖靈班未來會怎樣？

我們不妨參考下2005年成立的姚班“成果”：成立以來，到2019年已培養(yǎng)出375名本科生，大牛如云。

鬲融、貝小輝、馬騰宇、陳丹琦和吳佳俊等畢業(yè)生，已在杜克大學(xué)、南洋理工、普林斯頓和斯坦福等全球一流名校開始任教\研究。

17科滿分畢業(yè)的鬲融，還在2019年以其對深度學(xué)習(xí)中非凸優(yōu)化的研究，對于打造更精準(zhǔn)的神經(jīng)網(wǎng)絡(luò)極有助益，獲得諾獎風(fēng)向標(biāo)“斯隆獎”。

工業(yè)領(lǐng)域，備受矚目的AI獨(dú)角獸中，就有2家“姚班附屬創(chuàng)業(yè)公司”：曠視、小馬智行。

雖然清華姚班已經(jīng)有產(chǎn)出，北大雖然“晚”了一點(diǎn)，但現(xiàn)在勢頭一點(diǎn)不弱。

果然，中國最好的人才，給到最好的教育，一點(diǎn)也不輸世界頂尖高校和研究機(jī)構(gòu)。

清華姚班，北大圖靈，上交ACM…正在成為頂尖人才培養(yǎng)的新形勢、新潮流。

未來，待他們的畢業(yè)生走上科研、工作崗位，必將是中國算機(jī)領(lǐng)域新一代產(chǎn)學(xué)研中堅。

參考鏈接：

Mathematicians Begin to Tame Wild ‘Sunflower’ Problem

https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/

北京大學(xué)前沿計算研究中心：北京大學(xué)圖靈班本科生獲STOC最佳論文獎

https://mp.weixin.qq.com/s/bpC3FweuEtJZHRQJc7B3iQ

— 完 —