|
ACM計(jì)算理論年會(huì)（STOC）正在線上舉辦中。 最新消息，一位江蘇常州的小哥哥一口氣中了2篇論文，還拿下了最佳論文獎(jiǎng)。 而且他還是名本科生，首位拿下STOC最佳論文獎(jiǎng)的中國(guó)本科生。 沒(méi)錯(cuò)，就是那個(gè)理論計(jì)算機(jī)領(lǐng)域頂級(jí)會(huì)議，難度和含金量都穩(wěn)居第一梯隊(duì)的STOC。 他叫吳克文，畢業(yè)于江蘇常州中學(xué)，2016年被北京大學(xué)錄取，2017年成為北大圖靈班首屆學(xué)生，現(xiàn)在即將成為北大圖靈班首屆畢業(yè)生。 北大圖靈班，這個(gè)致力于為中國(guó)培養(yǎng)計(jì)算機(jī)科學(xué)界下一代領(lǐng)軍人物的國(guó)際化人才培養(yǎng)計(jì)劃，今年開(kāi)始交出了自己“答卷”： 同樣的優(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àn)的組合結(jié)構(gòu)，它表示若干兩兩相交均相同的集合。 1960年，數(shù)學(xué)家Paul Erd?s和Richard Rado提出了太陽(yáng)花猜想。 這一猜想有關(guān)于物體的幾何。以xy平面上的點(diǎn)的集合為例，首先需要確定的是在每個(gè)集合中包含的點(diǎn)的固定數(shù)量，然后開(kāi)始隨機(jī)畫環(huán)，讓每個(gè)環(huán)，或者說(shuō)每個(gè)集合都含有這一數(shù)量的點(diǎn)。環(huán)與環(huán)可以重疊，所以有的點(diǎn)可能會(huì)屬于不止一個(gè)集合中。 △圖源：QuantumMagazineErd?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ù)的研究都沒(méi)能突破w^w這個(gè)量級(jí)。 而這篇STOC 2020最佳論文，就是在這一問(wèn)題上實(shí)現(xiàn)了重大的突破——將約束改進(jìn)為約 (log w)^w。 也就是說(shuō)，將原來(lái)的結(jié)果改善了一個(gè)數(shù)量級(jí)！ 在這項(xiàng)研究中，吳克文和他的合作者們將問(wèn)題分解為兩種不同的場(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)集合沒(méi)有太多重疊時(shí)會(huì)發(fā)生什么。在這種情況下，最有可能產(chǎn)生太陽(yáng)花的方法是設(shè)置三個(gè)不相交的集合。 其中的難點(diǎn)在于，要證明三個(gè)完全獨(dú)立的集合隱藏在大量輕度重疊的集合中并非易事。 于是，研究人員將布爾函數(shù)運(yùn)用到了這個(gè)問(wèn)題中， 首先，為特定集合中的每個(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）是一種常見(jiàn)的布爾函數(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ú)疑問(wèn)展現(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年要求）：
但想要進(jìn)入其中并不容易——其每年只招收不超過(guò)30人。 2018年，北大圖靈班在原有計(jì)算機(jī)科學(xué)方向基礎(chǔ)上，新增了人工智能方向，每個(gè)方向招收30人，總共不過(guò)60人。 與姚班相同的是，北大圖靈班一樣人才輩出：吳克文是其中代表，但不僅僅只有吳克文。
現(xiàn)在，圖靈班迎來(lái)了首批畢業(yè)生，從他們頻頻透露出成果來(lái)看，這個(gè)答卷足夠優(yōu)秀。 北大圖靈班未來(lái)會(huì)怎樣？ 我們不妨參考下2005年成立的姚班“成果”：成立以來(lái)，到2019年已培養(yǎng)出375名本科生，大牛如云。 鬲融、貝小輝、馬騰宇、陳丹琦和吳佳俊等畢業(yè)生，已在杜克大學(xué)、南洋理工、普林斯頓和斯坦福等全球一流名校開(kāi)始任教\研究。 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./mathematicians-begin-to-tame-wild-sunflower-problem-20191021/ 北京大學(xué)前沿計(jì)算研究中心：北京大學(xué)圖靈班本科生獲STOC最佳論文獎(jiǎng) https://mp.weixin.qq.com/s/bpC3FweuEtJZHRQJc7B3iQ — 完 — |
|
|
