乘风破浪的博士：2019 ACM博士论文奖公布，清华姚班毕业生、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 以上。

在 ICLR 2019 最高产论文作者排名 中，吴佳俊名列在内。

今年 7 月，吴佳俊正式进入斯坦福大学，担任计算机科学系助理教授。

参考链接：https://awards.acm.org/about/2019-doctoral-dissertation