北大圖靈班本科生吳克文獲STOC 2020最佳論文獎

2021-01-10 機器之心Pro

機器之心報導

參與：澤南

今天，北京大學前沿計算研究中心官方公眾號報導稱，在全球計算機理論頂會 STOC 2020 上，北大本科生吳克文有兩篇論文發表，其中一篇獲得了最佳論文獎。

根據北京大學前沿計算研究中心官方公眾號的報導，6 月 25 日，ACM 計算理論年會 STOC 2020 上傳來一條好消息：北京大學信息科學技術學院 16 級圖靈班學生吳克文參與的論文《Improved bounds for the sunflower lemma》榮獲會議最佳論文獎。

作為計算機理論領域的全球頂級學術會議，ACM 計算理論年會（ACM Symposium on Theory of Computing，STOC）始於 1969 年，今年已經舉辦了 52 屆。

STOC 在整個計算機科學領域享有崇高的聲望，屬於公認難度最高的會議之一。與人工智慧不同，計算機理論領域被認為是國內學界與全球頂級水平相距較大的方向，在 STOC 大會中，2000-2017 年大陸研究機構平均每年發表的論文數量僅為 0.89 篇。

該會議由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主辦，歷年會議涵蓋的領域十分廣泛，包括算法和數據結構、計算複雜性、密碼學、計算幾何、組合學、隨機與去隨機化、算法博弈論和量子計算等。因新冠疫情影響，STOC 2020 於 2020 年 6 月 22-26 日在線舉行。

在中國計算機學會（CCF）最新版的推薦學術會議列表，以及清華大學發表的新版計算機學科推薦學術會議和期刊列表中，STOC 均被列為 A 類會議。

吳克文是北京大學信息科學技術學院圖靈班 16 級本科生，高中畢業於常州高級中學。他的科研興趣為理論計算機，如：複雜性理論、算法設計與分析、密碼學等。北大表示，作為圖靈班第一屆畢業生，吳克文將很快前往 UC Berkeley 繼續學習。

論文連結：https://dl.acm.org/doi/10.1145/3357713.3384234

這篇最佳論文由吳克文與 Ryan Alweiss、Shachar Lovett、Jiapeng Zhang 合作完成，主題是「太陽花引理的改進」。

太陽花（sunflower）是一種常見的組合結構，它表示若干兩兩相交均相同的集合。太陽花引理證明了，當我們有 「足夠多」 大小不超過 w 的集合時，我們必能從中找到太陽花。自 1960 年由 Erds, Rado 提出以來，儘管經歷了諸多改進，太陽花引理中的 「足夠多」 一直處於 w^w 量級。

在吳克文等人的論文中，他們將它改進到約 (log w)^w，更接近猜想的 O(1)^w。

由於太陽花結構的普遍性，該引理在計算機科學與組合數學中都有很多應用。

除了這篇論文之外，吳克文參與的另一篇論文——《Decision list compression by mild random restrictions（利用隨機賦值的決策表壓縮）》也被 STOC 2020 接收。

論文連結：https://dl.acm.org/doi/10.1145/3357713.3384241

此前，2016 年才有第一名國內本科生以一作形式在 STOC 上發表論文，他是來自清華姚班、計科 20 班的本科生鍾沛林，其論文是《分布流模型中的最優主成分分析》（Optimal Principal Component Analysis in Distributed and Streaming Models）。

吳克文之前，也曾有國人在 STOC 大會上獲獎。在去年的 STOC 2019 大會上，來自麻省理工學院的陳立傑獲得了最佳學生論文獎。

參考連結：https://mp.weixin.qq.com/s/bpC3FweuEtJZHRQJc7B3iQ

相關焦點

  • 中國本科生獲STOC最佳論文獎!北大圖靈班,正在頻頻交出答卷
    最新消息，一位江蘇常州的小哥哥一口氣中了2篇論文，還拿下了最佳論文獎。而且他還是名本科生，首位拿下STOC最佳論文獎的中國本科生。沒錯，就是那個理論計算機領域頂級會議，難度和含金量都穩居第一梯隊的STOC。他叫吳克文，畢業於江蘇省常州高級中學，2016年被北京大學錄取，2017年成為北大圖靈班首屆學生，現在即將成為北大圖靈班首屆畢業生。
  • 北大30人小班豪配兩位圖靈獎導師!清華有「姚班」,北大看「圖靈」
    英才輩出，有SIGGRAPH文章一作，還有STOC最佳論文 和隔壁的「姚班」一樣，北大圖靈班也是英才輩出。 今年6月，北大16級圖靈班學生吳克文在計算機科學領域頂級國際會議，第52屆ACM計算理論年會（STOC 2020）上發表了兩篇論文。
  • 北大30人小班豪配兩位圖靈獎導師!清華有「姚班」,北大看「圖靈」
    這個由圖靈獎獲得者John Hopcroft教授創立的班級，也是北大校園內「神一般」的存在。 昨天，北大靜園，首屆北京大學圖靈班 John Hopcroft 獎學金頒獎儀式在充滿古典氣息的五院「低調」舉行。 2017級圖靈班學生龔晨、2018級圖靈班學生潘樾陽等「少年天才」們獲頒此獎。
  • 信息科學技術學院本科生獲IEEE通信國際會議最佳論文獎
    北京大學信息科學技術學院2011級本科生廖昀、博士研究生王天宇、副教授邊凱歸、「百人計劃」特聘研究員宋令陽和美國休斯頓大學電子與計算機工程系副教授韓竹合作完成的論文《全雙工認知無線電中的分布式動態頻譜接入協議》（Decentralized dynamic spectrum access in full-duplex cognitive
  • 北大開設新結構經濟學實驗班 邀請諾獎得主親授
    今天晚上，在北京城市廣播《教育面對面》欄目「2020北京高招本科院校直播諮詢」中，北大心理與認知科學學院副院長、北京招生組老師姚翔介紹，除了在高考時填報專業志願，北大還為學生提供不少入校後二次選拔的機會。
  • CoRL2020獎項公布,斯坦福獲最佳論文獎,華為等摘得最佳系統論文獎
    來自史丹福大學和維吉尼亞理工的研究者摘得本屆 CoRL 會議的最佳論文獎，華為諾亞方舟實驗室和上海交大等機構學者榮獲最佳系統論文獎，南加州大學研究獲得最佳 Presentation 獎。昨日，第四屆機器人學習大會（CoRL）公布了最佳論文獎、最佳系統論文獎等獎項。
  • ACCV 2020最佳論文等三項大獎出爐!華為諾亞獲最佳學生論文獎
    ACCV 2020 共錄用論文 255 篇，官方提供所有論文開放下載。官網連結：http://accv2020.kyoto/截止目前，大會已經公布了最佳論文獎、最佳學生論文獎、最佳應用論文獎等三項大獎，其中帝國理工和華為諾亞方舟合作獲得了最佳學生論文獎。以下AI科技評論就帶大家讓我們一起來看看這三項大獎吧 ！
  • CIKM 2020最佳論文出爐!NUS和RMIT同獲最佳長論文獎
    作者 | 陳大鑫　　10月19日-10月23日，第29屆國際計算機學會信息與知識管理大會（CIKM 2020）在線上召開,官網：https://www.cikm2020.org/ 。　　以下介紹這兩篇最佳長論文。
  • ACM MM 2020大獎項出爐!南開獲最佳論文獎,西安交大獲最佳學生論文獎
    第28屆ACM國際多媒體會議（ACM MM）最佳論文獎、最佳學生論文獎、最佳demo獎、 最佳開源軟體獎在內的所有多媒體領域大獎都已出爐。其中最佳論文的一作是來自南開大學Hongru Liang，最佳學生論文的一作是來自西安交大的Wenbo Zheng。
  • 北大吳月芳獲中國天文學最高獎張鈺哲獎,80多歲仍在一線
    北大吳月芳獲中國天文學最高獎張鈺哲獎，80多歲仍在一線 「北大天文」微信公眾號 2020-10-12 18:53
  • 北京理工大學2020徐特立獎學金揭曉:10名本科生、10名研究生!
    陳釧法學院2017級本科生生源地高中：廣東省深圳市福田區深圳高級中學連續兩學期以100%的優良率年級排名第一榮譽及獎項獲第十一屆北京市大學生模擬法庭競賽一等獎、最佳書狀獎、第十屆北京市大學生模擬法庭競賽優秀個人獎；獲國家獎學金、一等優秀學生獎學金2次；獲評校級「優秀團幹部」、「優秀學生」等榮譽稱號。
  • 大三生獲最佳短論文獎,清華狂攬信息檢索頂會SIGIR2020多個獎項
    昨日，大會公布了最佳論文等獎項。來自清華大學的研究人員獲得最佳論文榮譽提名獎、最佳短論文獎獎項。ACM SIGIR 是信息檢索領域的頂級學術會議，今年是第 43 屆。據統計，SIGIR 2020 會議共收到投稿 1180 篇，接收 340 篇，接收率為 28.8%。
  • 2020版北大學霸上線!
    鄭宇軒曾獲國家獎學金、北大三好學生、校長獎學金、專項獎學金、五四獎學金等榮譽。02不負性命相託，致力臨床科研第三臨床醫學院2020級博士生高冠英2020年，高冠英以優異的成績通過了轉博考試，成為了北京大學第三臨床醫學院臨床醫學專業學位博士研究生。在北醫這個廣闊的舞臺上，他砥礪前行，踐行著醫者仁心的職責和擔當。
  • 工學院宋潔課題組成果獲年度IEEE TASE最佳論文獎
    with Patient Preference Learning」獲得了年度IEEE TASE Best Paper Award（最佳論文獎）。該獎的評選範圍是IEEE TASE 2019年發表的所有論文，獲獎結果於6月6日在2020年IEEE世界機器人與自動化大會（2020 IEEE International Conference on Robotics and Automation，簡稱IEEE ICRA）上宣布。
  • GPT-3獲NeurIPS最佳論文獎，華人學者獲經典論文獎
    包括GPT-3在內的三篇獲得最佳論文獎，一篇2011年論文獲得時間檢驗獎。最佳論文獎時間檢驗獎NeurIPS每年都會從大約十年前的大會上選取一篇論文，授予時間檢驗獎>（Test of Time Award，也稱經典論文獎），以表彰這篇論文對AI學界產生的持久而深遠的影響。
  • 戴彧虹等合作論文獲2011年國際通信大會最佳論文獎
  • CoRL 2020獎項公布,斯坦福最佳論文,華為等獲得最佳系統論文獎
    來自史丹福大學和維吉尼亞理工的研究者摘得本屆 CoRL 會議的最佳論文獎，華為諾亞方舟實驗室和上海交大等機構學者榮獲最佳系統論文獎，南加州大學研究獲得最佳 Presentation 獎。昨日，第四屆機器人學習大會（CoRL）公布了最佳論文獎、最佳系統論文獎等獎項。
  • 北大吳月芳獲中國天文學最高獎張鈺哲獎，80多歲仍在一線
    10月12日上午，在中國天文學會2020年學術年會開幕式上，北京大學天文學系吳月芳教授被頒發中國天文學會第十五屆張鈺哲獎。皓首窮經八十多歲高齡的吳月芳教授至今仍然活躍在科研一線，除自己進行科研外，還指導博士生和本科生，甚至長途飛行遠赴智利、夏威夷、西班牙等地的天文臺觀測；她更是我國紫金山天文臺青海站德令哈13.7米毫米波望遠鏡、上海天文臺佘山天馬65米射電望遠鏡、新疆天文臺南山
  • 中國科大一論文獲ACM Multimedia 2009最佳論文獎
    以中國科學技術大學博士生查正軍為第一作者的論文Visual Query Suggestion榮獲本次會議的最佳論文獎。　　在這篇論文中，作者針對目前基於文本的圖像檢索技術存在的檢索模糊問題，將「一圖勝千言」的思想融入到圖像檢索技術中，首次提出了一種聯合文本和圖像信息的圖像檢索方法（Visual Query Suggestion, VQS）。
  • 電子科技大學一博士獲PCIM Asia 2020最佳論文獎!
    會上，電子科技大學電子科學與工程學院博士生鄧高強的論文《Thermal Management for Buck Converters Using Co-packaged GaN Power HEMTs》榮獲大會唯一「最佳論文獎」（Best Paper Award）。