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

魚羊 乾明 2020-06-25 12:41:39 來(lái)源：量子位

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

ACM計(jì)算理論年會(huì)（STOC）正在線上舉辦中。

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

而且他還是名本科生，首位拿下STOC最佳論文獎(jiǎng)的中國(guó)本科生。

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

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

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

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

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

STOC是個(gè)什么樣的會(huì)議？

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

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

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

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

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

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

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

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

△圖源：QuantumMagazine

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

其后，他們證明了，這個(gè)“足夠多”的量級(jí)是w^w。

也就是說(shuō)，對(duì)包含100個(gè)點(diǎn)的集合來(lái)說(shuō)，要確保能找到一個(gè)由3個(gè)集合組成的太陽(yáng)花，需要100^100個(gè)集合。

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

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

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

也就是說(shuō)，將原來(lái)的結(jié)果改善了一個(gè)數(shù)量級(jí)！

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

第一種場(chǎng)景較為簡(jiǎn)單，即集合存在大量重疊的情況。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

北大圖靈班未來(lái)會(huì)怎樣？

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

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

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

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

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

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

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

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

參考鏈接：

Mathematicians Begin to Tame Wild ‘Sunflower’ Problem

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

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

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

— 完 —