機器之心報導
參與：魔王、杜偉、小舟
一年一度的 ACM 博士論文獎今日發布，畢業於特拉維夫大學的 Dor Minzer 獲得該獎項。榮譽提名獎則授予了瑞士洛桑聯邦理工學院（EPFL）博士 Jakub Tarnawski 和 MIT 博士吳佳俊。
今日，2019 ACM 最佳博士論文獎公布，畢業於特拉維夫大學的 Dor Minzer 獲得該獎項。此外，來自微軟的 Jakub Tarnawski 和出身清華姚班的吳佳俊獲得榮譽提名獎。
該獎項每年頒發一次，旨在獎勵計算機科學和工程領域最優秀的博士論文。畢業於特拉維夫大學的 Dor Minzer 博士憑藉論文《On Monotonicity Testing and the 2-to-2 Games Conjecture》獲得該獎項。
2019 ACM 最佳博士論文獎
這篇論文的主要貢獻是設置了測試布爾函數單調性的複雜度，並在解決 UGC（Unique Games Conjecture）方面取得了重大進展。UGC 是近似算法和複雜性理論中的最核心問題之一。
論文地址：http://www.cs.tau.ac.il/thesis/thesis/Minzer.Dor-Thesis-PhD.pdf
屬性測試器（property-tester）是非常高效的隨機化算法，當數據量太大無法檢查時，該算法可以確認對象是否滿足特定屬性。例如，檢查網際網路中任意兩臺計算機之間的距離不超過給定範圍。
在這篇論文的第一部分中，Minzer 提出一個能夠檢查布爾函數單調性的最優測試器，解決了該領域中的一個著名難題。
複雜性理論致力於將可計算問題分類為可行的和不可行的。PCP 定理（用於概率可檢查證明）建立了能夠將近似問題分類為不可行的框架，表明它們是 NP-hard 問題。2002 年，Subhash Khot 提出了 UGC，這一猜想激發了一系列的研究，並產生了深遠影響。如果該猜想被證明是正確的，則它將解釋整個算法問題大類的複雜性。
與其他猜想相反，UGC 一直存在爭議，社區中同時存在認可和質疑兩種聲音。儘管驗證該猜想的進展停滯不前，但關於該猜想的證據一直在積累，並且涉及到一些新的算法技術。
在該論文的第二部分，Minzer 進行了確立該猜想的另一半路程，在此過程中他證明了用於駁斥 UGC 的最有力證據無效。即使 UGC 不能很快得到解決，Minzer 的論文在解決之前無法解決的問題方面也取得了重大進展。
關於 Dor Minzer
Dor Minzer 博士畢業於以色列特拉維夫大學，現在新澤西州普林斯頓高等研究院（IAS）數學部做博後，將於 2020 年秋季加入 MIT 擔任助理教授。他的主要研究方向是計算複雜性理論、PCP 和布爾函數分析。
個人主頁：https://sites.google.com/view/dorminzer/home
2019 ACM 最佳博士論文榮譽提名獎
2019 ACM 最佳博士論文榮譽提名獎頒給了瑞士洛桑聯邦理工學院（EPFL）博士 Jakub Tarnawski 和 MIT 博士吳佳俊。
Jakub Tarnawski 獲獎論文：瞄準組合優化領域
Jakub Tarnawski 的博士論文《New Graph Algorithms via Polyhedral Techniques》對組合優化領域中兩個最核心的問題——匹配問題和旅行商問題（traveling salesman problem, TSP），做出了突破性算法進展。
論文地址：https://infoscience.epfl.ch/record/267500/files/
這篇博士論文針對匹配問題進行了確定性並行算法研究，這些工作受到計算機科學領域待解決難題——「隨機性是否有助於加速算法」的啟發。Tarnawski 的論文通過對擁有三十年歷史的隨機化並行匹配算法進行幾乎完全的非隨機化處理，實現了該問題的巨大突破。
該論文的另一項主要成果與旅行商問題相關，即找出給定 n 個城市的最短旅行路徑。1956 年，George Dantzig 等人利用線性規劃解決了該問題的一個特例。之後，其線性規劃成為組合優化領域中的主要開放性問題之一。Tarnawski 的論文漸進地解決了該問題，為不對稱旅行商問題提供了首個常數因子近似算法。
Jakub Tarnawski 博士畢業於瑞士洛桑聯邦理工學院（EPFL），現在谷歌研究院擔任研究員。研究興趣為理論計算機科學與組合優化，具體而言其研究重點是圖算法和近似算法。他參與的研究被 NeurIPS、ICML、SODA、MICCAI 等多個學術會議接收，並獲得 FOCS 2017、STOC 2018 的最佳論文獎。
個人主頁：http://jakub.tarnawski.org/
吳佳俊獲獎論文：探索 AI 感知物理世界的能力
吳佳俊在博士論文《Learning to See the Physical World》中，通過集成神經網絡中自下而上的識別引擎和自上而下的模擬引擎、圖模型和概率規劃，推動 AI 在感知物理世界方面的發展。
論文地址：https://jiajunwu.com/papers/dissertation.pdf
儘管人工智慧在過去十年間取得了顯著進步，但當前的 AI 方法只能解決特定問題，需要大量的訓練數據，並且在泛化至新任務或新環境時容易崩潰。人類智能揭示了人工智慧的發展之路還有多遠：給出單張圖像，人類可以解釋看到的事物，重建 3D 場景，預測即將發生的事情，以及做出行動規劃。
吳佳俊的博士論文的主題是物理場景理解，即如何構建能夠學習觀察和推理物理世界並與之交互的高效通用機器。其核心思路是：將計算機圖形學、物理學和語言學中的模擬引擎，與深度學習進行集成，進而充分挖掘物理世界的因果結構。
這篇博士論文涵蓋感知、物理和推理多個領域的內容，旨在培養像人類一樣觀察和推理物理世界的人工智慧。此外，該論文融合了人工智慧的多個分支，解決了感知、動態建模和認知推理多個方面的關鍵問題。
論文作者吳佳俊現為史丹福大學計算機科學系助理教授。他本科畢業於清華大學姚班，之後在麻省理工學院（MIT）相繼完成碩博階段的研究學習。他的研究興趣包括物理場景理解、動態模型和多模態感知。
個人主頁：https://jiajunwu.com/
吳佳俊的人生履歷堪稱傳奇。他是清華大學交叉信息研究院 2010 級本科生，隨後進入姚班學習。本科期間曾連續三年學分績全年級第一，並榮獲清華大學本科生特等獎學金、蔣南翔獎學金和姚期智獎學金等。此外，吳佳俊還榮獲了第九屆中國青少年科技創新獎。
在學術方面，吳佳俊有多篇論文被 CVPR、ICLR、ICML、NeurIPS 等世界頂級學術會議接收。據 Google Scholar 數據顯示，他至今已發表 77 篇論文，被引用數 4300 以上。
中，吳佳俊名列在內。
今年 7 月，吳佳俊正式進入史丹福大學，擔任計算機科學系助理教授。
參考連結：https://awards.acm.org/about/2019-doctoral-dissertation
歡迎全球開發者共同參與華為HMS全球應用創新大賽，亞太， 歐洲，拉美，中東非、中國五大賽區報名將同時開啟。華為耀星計劃提供100萬美金創新激勵金，提供全平臺資源全球激勵開發者創新。誠邀全球應用開發者參賽，一起創新重構未來。點擊閱讀原文，立即報名。
原標題：《乘風破浪的博士：2019 ACM博士論文獎公布，清華姚班畢業生、MIT學霸吳佳俊獲榮譽提名》
閱讀原文