FOCS 2019重磅來襲,清華姚班畢業生陳立傑連中三元

2020-12-05 騰訊網

新智元推薦

來源：會議之眼

【新智元導讀】2019頂會上，深度學習大神、亞馬遜AI主任科學家李沐此前便是FOCS獲獎者，而MIT博士生、清華姚班畢業生陳立傑今年一連中獎3篇，並榮獲最佳學生論文獎。來新智元 AI 朋友圈與AI大咖一起討論吧～

會議之眼A類、CCF A類會議FOCS（Foundations of Computer Science）是由IEEE計算機協會計算數學基礎技術委員會主辦的國際頂會！大會致力於為計算機理論的基礎研究和新方法開創領域的研究者提供一個交流和展示的平臺。其高逼格、難搞定的程度讓不少科研工作者只得仰望。深度學習大神、亞馬遜AI主任科學家李沐此前便是FOCS獲獎者，而MIT博士生、清華姚班畢業生陳立傑今年一連中獎3篇，並榮獲最佳學生論文獎。

FOCS每年舉辦一次，第60屆計算機科學基礎IEEE研討會定於2019年11月9日至12日在美國馬裡蘭州最大城市巴爾的摩召開。論文提交截止日期為同年4月5日，接收公布日期為7月1日。小程序會議之眼plus提供了會議時間、地點、等級和官網查詢地址。致力於在計算機基礎理論研究領域發Paper的小夥伴要早做規劃，及時收藏呀！

最佳論文

Lower bounds for maximal matchings andmaximal independent sets

Alkida Balliu,Sebastian Brandt,JuhoHirvonen,Dennis Olivetti,Mika l Rabie, Jukka Suomela

論文簡介：

在O（Δ+ log n）的通信回合中，存在用於找到最大匹配和最大獨立集的分布式圖形算法。這裡n是節點數，Δ是最大度。Linial的下限表明對n的依賴是最優的：即使Δ= 2，這些問題也無法在O（Δ+ log n）輪中解決。但是，對Δ的依賴性是一個長期存在的懸而未決的問題，目前在上下限之間存在指數差距。

作者證明上限是緊密的。在分布式計算的本地模型中，使用任何隨機算法都無法在O（Δ+ loglogn / logloglogn）輪次中找到最大匹配和最大獨立集。因此，沒有一個確定的算法可以在O（Δ+ logn / loglogn）輪次中運行最大匹配或最大獨立集。這可以作為n的函數對先前的下限進行改進。

NEEXP MIP*

Authors: AnandNatarajan,John Wright

論文簡介：

作者研究了multiprover交互式證明系統。證明了經典的multiprover交互證明系統的作用，其主要結果是等式MIP = NEXP。事實證明，量子多重證明者交互式證明系統的功能難以證明，其中證明者可以共享糾纏。Ito和Vidick曾提出了MIP *的最著名下限是NEXP。至於上限，MIP *可以和RE一樣大。

這項工作的主要結果是在提出了MIP *的NEEXP（不確定的雙指數時間）。這是對先前下限的一個指數改進，表明具有糾纏證明者的證明系統至少比經典證明者在指數上具有更大的功能。在作者的協議中，驗證者將經典的NEEXP，指數上的MIP協議委派給兩個糾纏證明者：證明者通過測量其共享狀態來獲得其指數問題，並使用經典PCP來證明其答案的正確性。至關重要的是協議的穩健性，每個參與者不僅應該正確地對自己的問題進行抽樣，而且還應避免會洩露其他參與者的抽樣問題的情況出現。

Automating Resolution is NP-Hard

Albert Atserias,Moritz Müller

論文簡介：

作者發現駁斥解決的問題在於非確定性多項式複雜度的歸約問題。在證明複雜性方面，除非P = NP，否則解決方案無法自動執行。區分具有多項式長度的解析度反駁的公式和不具有次指數長度反駁的公式是非確定性多項式複雜度的歸約問題。這也意味著，除非在SUBEXP或QP中分別包含NP，否則解析度無法在指數以下的時間或準多項式時間內自動執行。

最佳學生論文

EfficientConstruction of Rigid Matrices Using an NP Oracle

Josh Alman, Lijie Chen

Faster Minimum k-cut of a Simple Graph

Jason Li

小助手已經打包整理好上述文章，關注計算機科學基礎研究的朋友們快快收藏起來!閱讀頂會最佳論文，關注最新動態！

相關焦點

  • 姚班學霸陳立傑:16歲保送清華,18歲拿下IOI世界冠軍
    ，成為2016年十位清華特等獎學金獲獎者之一； 24歲，拿下理論計算機科學領域最頂級會議STOC 2019 DannyLewin最佳學生論文獎，名聲大振； 在最近第60屆IEEE計算機科學基礎年度研討會（FOCS 2019）上，他不僅一口氣發表了3篇論文，還獲得了最佳學生論文獎。
  • 「網癮學霸」陳立傑:18歲獲奧賽金牌進姚班,曾得清華特等獎學金
    雖然今年只有25歲，但他在計算機領域已經是閃閃發光的「明星」：16歲，拿下全國青少年奧林匹克競賽的金牌，保送清華；18歲，以世界第一名的成績，斬獲國際信息學奧林匹克競賽（IOI）金牌，進入清華姚班；21歲，獲得2016年清華特等獎學金；
  • 最強大腦的趙金昊,千萬年薪的清華姚班,到底是怎樣的一種存在
    隨著新一季最強大腦的開播，屢屢刷屏的清華姚班再次出現在了公眾的視野中，那麼，這個傳說中的天才集訓營究竟有多牛呢？在清華有這樣一句話：半國英才聚清華，清華精英在姚班。由此可見，姚班的學生乃是精英中的精英了。
  • 清華姚班出身,95後博士生陳立傑獲理論計算機頂會最佳學生論文
    【新智元導讀】理論計算機科學領域最頂級的國際會議STOC最佳學生論文獎，頒給清華姚班畢業生、MIT陳立傑等人，陳立傑在中學、大學本科階段，創造了無數神話，連清華大學老師都直呼他是」神人「。95後的理論計算機科學家來了。
  • 新清華十大學神之陳立傑:「打遊戲」上清華的另類學神!
    【鼎恆商學院新聞中心 一哲】2020高考就快要到了，所以鼎恆商學院新聞中心記者特別推出新清華十大學神系列，為各位學子講述他們的傳奇經歷，希望能為處於高考前夕的學子們加油打氣，助力考出理想的分數。今天，記者要為大家分享的是新清華十大學神之陳立傑的故事。陳立傑同樣畢業於清華大學計算機系實驗班（俗稱姚期智班、姚班）。而在天才、大神雲集的姚班裡，陳立傑又是最特殊的那一個。為什麼說他特殊呢？
  • 清華裡傳奇的「姚班」,到底有多牛?混得最差的學生也已年入百萬
    不過，大學已不存在教育公平這麼一說了，高考就已經將學生質素劃分成了三六九等，其職責是讓學生更加專精發展，因此開辦「尖子班」無可厚非。 而要說到大學裡的尖子班，清華的「姚班」絕對是一座繞不過去的豐碑。這個尖子班向來有「清華中的清華」這麼一說，這裡畢業出去的學生，混得最差的如今也早已年入百萬。而這個「姚班」到底是什麼一個來頭，且聽筆者慢慢道來。
  • 清華北大算個啥,進這些班級才算牛!姚班,智班,圖靈班你知多少?
    一、清華姚班、智班、經管學院 1、清華姚班 百萬年薪招不到清華「姚班」畢業生 「半國英才聚清華，清華英才聚姚班」，說起清華姚班，曾經有一個「佳話」被大家熟知
  • 清華又出一個姚班!AI班成立,姚期智任首席教授,首批招生30人
    在昨天的開放日上，清華宣布成立人工智慧學堂班。根據新京報報導，這個班級將成為清華學堂人才培養計劃第八個實驗班。同時，它也將是清華大學的第二個「姚班」。因為，這是圖靈獎得主、清華大學交叉信息院院長姚期智院士第二次出任首席教授。
  • 清華最牛學院?同時擁有姚班、智班,匯聚各方學霸!
    ，在千萬學生中能夠脫穎而出，金榜題名，不容易，要知道每年清華的招生人數是很少的，每個省都屈指可數，這些人都是超級學霸。任何一個人都可以稱為是天之驕子，但是在清華裡也存在著王牌班級和本科群體，其中姚班和智班就是清華最好的學生群體，姚班建立於2005年，是由清華教授姚期智先生開創，目的是為了培養國際性計算機人才，而且姚班從創建至今的14年時間裡已經培養了375名優秀的畢業生。
  • 陳立傑:從網癮少年蛻變成清華學霸,24歲最佳論文獎「連中三元」
    陳立傑和那些得過且過的「同類」唯一的不同，就是他對於計算機的熱愛與痴迷，這是他願意無悔付出的全部。在初中同學們都忙著上各式各樣的數理化補習班時，陳立傑卻開始自學計算機編程，憑藉著自己的熱愛去參加信息學競賽。但所有的努力都在他名落孫山後化為泡影，甚至連一向對他包容的父母也勸他放棄，希望它能把自己的時間用在提高自己的學習成績上。
  • 清華「姚班」和「智班」:每班3名女生,江蘇最強,兩個大省0人
    今天，「贏在高三」通過清華大學「姚班」和「智班」的學生來源，和大家一起來討論這個問題。為什麼要選擇清華大學的「姚班」和「智班」呢？因為在清華大學流傳著這麼一句話：半國英才聚清華，而清華一半英才在姚班和智班。
  • 清華姚班畢業生開發新特效程式語言,99行代碼實現《冰雪奇緣》
    關於Taichi，胡同學已經發表了多篇文章，分別被SIGGRAGH 2018、ICRA 2019、NeurIPS2019、ICLR 2020等頂會收錄。計算機圖形學知名學者、北大教授陳寶權給出很高的評價：給胡淵鳴同學點讚！一己之力開發了物理模擬程式語言 Taichi！
  • 清華姚班、麻省理工博士胡淵鳴:99 行代碼實現《冰雪奇緣》
    胡淵鳴高一保送清華，競賽生涯中，胡淵鳴拿下APIO 2012、NOI 2012、ACM-ICPC 2013長沙區域賽、ACM-ICPC上海區域賽四塊金牌，其中APIO 2012成績是全場第一名。2013年進入清華姚班，胡淵鳴與陳立傑、範浩強等人成為同班同學，這群年輕人的才華在這裡匯聚、碰撞，與「姚班」二字相互成就。
  • 清華智班姚班有多牛?匯聚各方高考狀元和奧賽冠軍,畢業年薪百萬
    我國最好的大學當屬北京大學和清華大學，這兩所大學在全世界的排名也越來越高，而在我國最頂尖的大學裡，各個專業各個班級的實力也不盡相同，清華大學最好的兩個班級是智班和姚班，我們都知道想在高考中考上清華並非易事，需要極高的分數才行，每年清華北大兩所學校分配到各省的名額數量也是屈指可數的，能夠進入這兩所學府中的任何一所都堪稱超級學霸了
  • 清華姚班畢業生,從谷歌辭職回家教書?本人:不想為成功捨棄一切
    他是2009級清華姚班畢業生，清華碩士畢業後就職於摩根大通、谷歌……而更早之前，他還是NOI金牌得主，在數學、物理和信息學方面很早就展露天才，更後來從山西省實驗中學保送清華，進入姚班。第一次選擇：放棄未完成的博士，離開科研張昆瑋生於山西晉中，初中畢業以全省第一成績考入山西省實驗中學，很快就在數學、物理和信息學競賽中嶄露頭角，拿到兩個省級一等獎，並且榮膺全國信息學奧賽金牌，最終成功保送清華。
  • 他們4人是杭州學軍中學數學天才、信息學高手……同進2020清華姚班
    2020清華姚班、智班76名學生分班名單「清華學堂計算機科學實驗班」（又稱「姚班」），由國際著名計算機科學家姚期智院士於2005年創辦，致力於培養與美國麻省理工學院、普林斯頓大學等世界一流高校本科生具有同等、甚至更高競爭力的領跑國際拔尖創新計算機科學人才。
  • NOL金牌、清華姚班畢業生放棄谷歌,回鄉任教工資3000,徵婚被贊
    最近，某徵婚網站一則代朋友網上徵友的貼子爭起人們的關注，該帖稱徵友者是山西的清華本碩男生，畢業於清華大學姚班，曾在摩根大通和谷歌當過程式設計師，後回到老家山西，進入晉中學院當青年教師，工資僅3000多，而且自己不喜歡科研，因此晉升職稱無望，不過課外能接私活，勉強上萬。
  • 保送清華姚班,17科滿分大神,32歲斬獲「諾獎風向標」斯隆獎
    交上成績單：保送清華姚班，成17科滿分大神從高中起，鬲融開始參加全國性計算機競賽。2002年到2004年，鬲融連續兩屆獲得全國信息學奧林匹克競賽金牌，初露鋒芒，接著在第16屆國際信息學奧林匹克競賽中，他代表國家隊斬獲國際金牌。
  • 清華姚班VS北大英才班,哪個班生源更好,數據顯示了真實結果
    清華姚班基本代表了清華的最高水平生源，而北大的英才班自然也是北大生源的最高水準，那麼這兩個班哪個生源更為強悍呢？其一是中國數學奧林匹克全國決賽一等獎；其二是數學特長，並在國內外數學專業相關學習實踐活動中取得優異成績者。 而在2020年這屆的英才班中，清一色的國家集訓隊和CMO一等獎獲得者。還有60屆IMO金牌獲得者，和61屆IMO國家隊成員。這些全部都是高二學生，英才班真可謂名不虛傳。
  • 清華最強本科畢業生Top10出爐:從沒有什麼天才學霸
    CVPR 2019、ICML 2019和NeurIPS 2020，都被其盡數收入囊中。前往ICML現場做20分鐘口頭報告，給臺下的上百個同行們講解自己的工作，讓我有一種代表清華精神的使命感。交流與合作真是無處不在，不僅是匯報如此，在研究中也是如此。在劉同學的論文合作者中，我們能看到許多熟悉的大牛名字。