Mihai Pătrașcu 最佳论文奖：Seth Pettie 客座投稿

理论计算机科学领域的一个重要奖项——SOSA 最佳论文奖，现已更名为“米哈伊·帕特拉什库奖”，以纪念这位英年早逝的杰出学者。帕特拉什库在其短暂的职业生涯中，对数据结构和算法领域产生了深远影响，以其深刻的洞察力而闻名。SOSA 研讨会的核心理念是推崇算法的简洁与洞见，这与帕特拉什库的研究精神高度契合，因此更名是对其学术遗产的致敬。2026 年的获奖论文是关于圆图三色问题的准多项式时间算法。

一位早逝的天才与不朽的贡献

米哈伊·帕特拉什库 (Mihai Pătrașcu) 是一位杰出的理论计算机科学家，于 2012 年因脑癌不幸去世，年仅 29 岁。尽管他的研究生涯（2004-2012）十分短暂，但他对整个领域产生了巨大而深远的影响。

    • 影响广泛： 他的研究覆盖几何、图算法、数据结构，尤其是在下界 (lower bounds) 领域。
    • 重振领域： 他以一己之力重振了细胞探针下界 (cell-probe lower bounds) 和简洁数据结构 (succinct data structures) 等研究领域。
    • 奠定基础： 他为细粒度复杂性 (fine-grained complexity) 理论奠定了基础，并首次给出了图问题的 3SUM-hardness 证明。
    • 挑战难题： 他对著名的动态最优性猜想 (dynamic optimality conjecture) 发起了迄今为止最成功的攻击。

他的论文读起来是一种真正的享受——充满趣味和对理论计算机科学的热爱。

简洁与洞见：SOSA 的核心价值

SIAM 简约算法研讨会 (SOSA) 创立于 2018 年，其核心理念在于，简洁性 (simplicity) 是一种极其宝贵、稀有且被严重低估的品质。SOSA 旨在创建一个以简洁和洞见 (insight) 作为首要成功标准的学术平台。

将该奖项以米哈伊的名字命名是极为恰当的。他总是能为他所研究的每个问题带来“全新的视角”，并向我们展示解决问题的关键通常在于找到那一个核心的洞见。

我们问题的解决方案，通常就是一个关键的洞见（当然还需要一些数学上的技巧）。

2026 年米哈伊·帕特拉什库最佳论文奖

SOSA 2026 年的获奖论文体现了这一精神，其具体信息如下：

    • 获奖论文： 《圆图三色问题的准多项式时间算法》(A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs)
  • 获奖作者：
      • Ajaykrishnan E S
      • Robert Ganian
      • Daniel Lokshtanov
      • Vaishali Surianarayanan
    • 颁奖典礼： 该奖项将于 2026 年 1 月 12 日在加拿大温哥华举行的 SODA/SOSA 会议期间颁发。