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

skysun000001 2020-06-25

展開全文

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

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

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

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

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

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

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

北大學霸斬獲STOC最佳論文獎

STOC是個什么樣的會議？

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

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

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

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

△論文畫風長這樣

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

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

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

△圖源：QuantumMagazine

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.成績優(yōu)良，已修課程績點≥3.0。
2.已修數(shù)學A類課程（《數(shù)學分析I》和《高等代數(shù)I》）成績≥80分，且《計算概論A》成績 ≥85分；本學期在修《數(shù)學分析II》和《高等代數(shù)II》。
3.非信息科學技術(shù)學院的學生報名，須在校內(nèi)門戶提交轉(zhuǎn)院（系）轉(zhuǎn)專業(yè)申請。

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

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

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