帕辛·马努朗西：证明计算机无法完成的任务

2011年7月，泰国度假城市芭堤雅举办了第23届国际信息学奥林匹克竞赛（IOI），这是泰国首次举办该项赛事，时任总理阿披实·威差奇瓦（Abhisit Vejjajiva）出席并主持了开幕式。在东道主队伍中，有一名来自曼谷基督教学院（Bangkok Christian College）的学生，他以524分的成绩在303名参赛者中名列第14位，并连续第二年获得金牌。他向记者表示对第14名的成绩感到满意，并称524分超出了预期，同时希望举办此次奥赛能激发泰国青年对计算机的兴趣。十五年后，帕辛·马努朗西（Pasin Manurangsi）已成为专门负责界定哪些计算机问题属于“无解”范畴的研究员之一。

奥赛之路

马努朗西的竞赛经历犹如一场精心设计的提升实验。在2009年保加利亚举行的IOI比赛中，他以516分的成绩在301名选手中排名第67位，获得银牌。2010年在加拿大，他以704分获得第12名，摘得金牌。2011年，在主场作战时，他再次夺得金牌，并助力泰国队在首次承办的赛事中获得团体金牌。三次参赛，两金一银，且从首次到第二次尝试之间世界排名跃升了五十五位：这是一个将失利视为规范文档而非最终裁决者的成长轨迹。

麻省理工学院与“近邻”问题

马努朗西在麻省理工学院（MIT）获得了学士和硕士学位，其硕士论文在达娜·莫什科维茨（Dana Moshkovitz）的指导下，研究投影博弈（projection games）的近似算法。这一选题方向确定了他后续研究的主旨。近似算法是计算机科学中一种务实的折衷方案：当问题无法在合理时间内得到精确解时，退而求其次，寻找一个能够保证在最优解一定误差范围内的解。有趣且马努朗西反复探讨的问题是：在触及数学壁垒之前，这种解的保证程度究竟能达到多高？

加州大学伯克利分校：P与NP之间的地带

他于2019年5月在加州大学伯克利分校（University of California, Berkeley）获得博士学位，由卢卡·特雷维桑（Luca Trevisan）和普拉萨德·拉加文德拉（Prasad Raghavendra）共同指导，尼基尔·斯里瓦斯塔瓦（Nikhil Srivastava）担任委员会成员。博士论文题为《近似与硬度：超越P与NP》（Approximation and Hardness: Beyond P and NP），其志向从标题中可见一斑。经典的复杂性理论将问题分为易解（P）和著名的困难（NP完全）问题。马努朗西的论文专门探索了这些范畴之外的领域：既不属于P又不确定为NP困难的问题，例如k-支配集（k-dominating set）、k-团（k-clique）、k-双团（k-biclique）、有向斯坦纳网络（directed Steiner network）和格问题（lattice problems），以及最违反直觉的、位于P类问题内部但仍难以快速近似的问题，如最近对（closest pair）和最大内积（maximum inner product）。摘要称该工作解决了参数复杂性领域两个长期悬而未决的问题，并为多个问题提供了已知的最佳不可近似性因子。这是一篇关于划定边界而非跨越边界的论文。

最稠密k-子图壁垒

使他声名鹊起的一项单一成果涉及“最稠密k-子图”（Densest k-Subgraph）问题：给定一个网络，找出连接最紧密的k个节点。马努朗西证明，在指数时间假设下，没有多项式时间算法能实现优于n的1/(log log n)常数次方的近似比——而在更强的Gap-ETH假设下，该壁垒缩小至n^f(n)（对于任何趋近于零的函数f），这几乎等同于多项式硬度。至关重要的是，该构造具有领域内所谓的“完美完备性”：它能区分确实包含k-团的图与每个k-子图都稀疏的图。该论文获得了2017年理论计算机科学旗舰会议STOC的丹尼·莱文最佳学生论文奖（Danny Lewin Best Student Paper Award）。

谷歌、隐私与公平分配

自2019年7月以来，马努朗西一直在谷歌研究院（Google Research）担任研究科学家，其列出的领域包括算法与理论、机器智能和反滥用，并已发表了一百多篇论文。研究重心已从纯粹的不可近似性转向差分隐私、学习理论和计算社会选择，如公平分配、共识平分、私有排名聚合和合成数据生成。近期的一项成果表明，对于具有单调效用的n个代理，始终存在达O(√(n log n))的共识平分方案，这改进了之前的界限。奖项纷至沓来：2021年WAOA最佳论文、2021年ALT最佳学生论文、2026年FORC最佳论文及最佳论文荣誉奖，此外还获得了2021年和2023年IJCAI杰出程序委员会表彰，以及2023年NeurIPS顶级审稿人称号。

回归之旅

自2022年起，他开始参与泰国信息学奥赛及其数学奥赛集训队的指导工作，并作为嘉宾代表团成员参加了2024年IOI。自2023年起，他还担任CMKL大学的兼职教员，教授算法、数据结构和隐私保护算法。曾经成就他的培养系统，如今正有他的助力参与运行。

为什么帕辛被称为天才

这里涉及的认知质量非常独特，并非单纯的速度。奥赛成功奖励的是在时间压力下快速、准确地解决问题的能力；而近似硬度研究奖励的恰恰相反——即通过构建精密的还原证明来证明某一类算法注定失败的耐心。马努朗西罕见地在两个层面上都表现卓越，而伯克利大学的博士论文就是明证：它开辟了一个大多数研究人员避之不及的领域，原因在于负面结果更难发表，也更难保证准确性。还原证明中任何一个逻辑疏漏都会导致全盘皆输。

一个诚实的对比观点同样重要。在现有的所有来源中——包括他自己的主页、Google研究院资料、博士论文，甚至当时的泰国媒体报道——都没有使用“天才”一词来形容他。他的荣誉均来自会议委员会颁发的同行奖项，旨在表彰当下的最佳论文，而非超越时代的头脑。理论计算机科学也极其依赖合作；他发表的一百多篇论文都是共同署名、研讨会以及伯克利由该领域两位顶尖复杂性理论家领导的团队的产物。虽然他的IOI记录非常优秀，但也包括过第67名的排名。如果不进行过度夸大，事实更为窄小且有趣：他是数学中最具技术挑战性的领域之一的一流专业人士，其决定性的研究成果解决了一个多年悬而未决的问题。这与所谓的天才并不相同，他也从未声称自己是天才。

前景展望

马努朗西的职业生涯对于理论家而言有着不同寻常的轨迹：先是不可能性证明，后是应用隐私研究。转向差分隐私和公平分配表明，他在确定了边界位置后，更倾向于在边界内进行创造。泰国奥赛的教练工作或许会成为他更持久的遗产——一个曾经举办过IOI的国家，如今正在培养那些能够赢得它的人。