北大圖靈班本科生吳克文獲STOC 2020最佳論文獎(jiǎng)

今天，北京大學(xué)前沿計(jì)算研究中心官方公眾號(hào)報(bào)道稱，在全球計(jì)算機(jī)理論頂會(huì) STOC 2020 上，北大本科生吳克文有兩篇論文發(fā)表，其中一篇獲得了最佳論文獎(jiǎng)。

根據(jù)北京大學(xué)前沿計(jì)算研究中心官方公眾號(hào)的報(bào)道，6 月 25 日，ACM 計(jì)算理論年會(huì) STOC 2020 上傳來一條好消息：北京大學(xué)信息科學(xué)技術(shù)學(xué)院 16 級(jí)圖靈班學(xué)生吳克文參與的論文《Improved bounds for the sunflower lemma》榮獲會(huì)議最佳論文獎(jiǎng)。 作為計(jì)算機(jī)理論領(lǐng)域的全球頂級(jí)學(xué)術(shù)會(huì)議，ACM 計(jì)算理論年會(huì)（ACM Symposium on Theory of Computing，STOC）始于 1969 年，今年已經(jīng)舉辦了 52 屆。 STOC 在整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，屬于公認(rèn)難度最高的會(huì)議之一。與人工智能不同，計(jì)算機(jī)理論領(lǐng)域被認(rèn)為是國(guó)內(nèi)學(xué)界與全球頂級(jí)水平相距較大的方向，在 STOC 大會(huì)中，2000-2017 年大陸研究機(jī)構(gòu)平均每年發(fā)表的論文數(shù)量?jī)H為 0.89 篇。 該會(huì)議由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主辦，歷年會(huì)議涵蓋的領(lǐng)域十分廣泛，包括算法和數(shù)據(jù)結(jié)構(gòu)、計(jì)算復(fù)雜性、密碼學(xué)、計(jì)算幾何、組合學(xué)、隨機(jī)與去隨機(jī)化、算法博弈論和量子計(jì)算等。因新冠疫情影響，STOC 2020 于 2020 年 6 月 22-26 日在線舉行。 在中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）最新版的推薦學(xué)術(shù)會(huì)議列表，以及清華大學(xué)發(fā)表的新版計(jì)算機(jī)學(xué)科推薦學(xué)術(shù)會(huì)議和期刊列表中，STOC 均被列為 A 類會(huì)議。

吳克文是北京大學(xué)信息科學(xué)技術(shù)學(xué)院圖靈班 16 級(jí)本科生，高中畢業(yè)于常州高級(jí)中學(xué)。他的科研興趣為理論計(jì)算機(jī)，如：復(fù)雜性理論、算法設(shè)計(jì)與分析、密碼學(xué)等。北大表示，作為圖靈班第一屆畢業(yè)生，吳克文將很快前往 UC Berkeley 繼續(xù)學(xué)習(xí)。

論文鏈接：https://dl.acm.org/doi/10.1145/3357713.3384234 這篇最佳論文由吳克文與 Ryan Alweiss、Shachar Lovett、Jiapeng Zhang 合作完成，主題是「太陽花引理的改進(jìn)」。 太陽花（sunflower）是一種常見的組合結(jié)構(gòu)，它表示若干兩兩相交均相同的集合。太陽花引理證明了，當(dāng)我們有 「足夠多」大小不超過 w 的集合時(shí)，我們必能從中找到太陽花。自 1960 年由 Erd?s, Rado 提出以來，盡管經(jīng)歷了諸多改進(jìn)，太陽花引理中的 「足夠多」一直處于 w^w 量級(jí)。 在吳克文等人的論文中，他們將它改進(jìn)到約 (log w)^w，更接近猜想的 O(1)^w。 由于太陽花結(jié)構(gòu)的普遍性，該引理在計(jì)算機(jī)科學(xué)與組合數(shù)學(xué)中都有很多應(yīng)用。 除了這篇論文之外，吳克文參與的另一篇論文——《Decision list compression by mild random restrictions（利用隨機(jī)賦值的決策表壓縮）》也被 STOC 2020 接收。 論文鏈接：https://dl.acm.org/doi/10.1145/3357713.3384241 此前，2016 年才有第一名國(guó)內(nèi)本科生以一作形式在 STOC 上發(fā)表論文，他是來自清華姚班、計(jì)科 20 班的本科生鐘沛林，其論文是《分布流模型中的最優(yōu)主成分分析》（Optimal Principal Component Analysis in Distributed and Streaming Models）。 吳克文之前，也曾有國(guó)人在 STOC 大會(huì)上獲獎(jiǎng)。在去年的 STOC 2019 大會(huì)上，來自麻省理工學(xué)院的陳立杰獲得了最佳學(xué)生論文獎(jiǎng)。