Pasin Manurangsi: コンピュータが何を実行できないかの証明

2011年7月、タイの観光都市パッタヤー（Pattaya）で第23回国際情報オリンピックが開催された。これはタイにとって初の開催であり、アピシット・ウェッチャチーワ（Abhisit Vejjajiva）首相が最後の公務の一つとして開会式を行った。地元チームには、バンコク・クリスチャン・カレッジ（Bangkok Christian College）の生徒が含まれており、彼は303人の競技者の中で524点を獲得し、14位に入賞して2年連続の金メダルを獲得した。彼は記者団に対し、14位という結果に満足しており、524点というスコアは予想以上だったと語り、オリンピックの開催によってタイの若者の間でコンピュータへの関心が高まることを望んでいると述べた。15年後、Pasin Manurangsiは、コンピュータ科学の残りの分野に対して、どの問題が絶望的であるかを告げる役割を担う研究者の一人となっている。

オリンピックの軌跡

Manurangsiの競技成績は、改善のための制御された実験のように読める。ブルガリアで開催された2009年のIOIでは、516点を獲得し301人中67位で銀メダルを獲得した。2010年のカナダ大会では704点を獲得し297人中12位で金メダルを獲得した。2011年の地元開催では、タイが初めて主催した競技会で団体金メダルを獲得し、彼自身も再び金メダルを獲得した。3回の出場で金2、銀1、そして初挑戦と2回目の試みの間での世界ランキング55位のジャンプは、敗北を評決ではなく仕様書として扱った人物の軌跡である。

MITと十分に近づくことの難しさ

Manurangsiはマサチューセッツ工科大学（MIT）で学士号と修士号を取得し、Dana Moshkovitzの指導を受けた修士論文では、プロジェクションゲーム（projection games）の近似アルゴリズムを扱った。そのトピックの選択が、その後のすべての方向性を決定した。近似は計算機科学における実用的な妥協案であり、ある問題を妥当な時間内に正確に解くことができない場合、最良の解に対する一定の範囲内に収まる保証のある答えで妥協する。Manurangsiが繰り返し立ち返った興味深い問いは、その保証が数学的な壁に突き当たるまでに、どれほど優れたものになり得るかということだった。

バークレー：PとNPの間の大地

彼は2019年5月、カリフォルニア大学バークレー校で博士号を取得した。指導教官はLuca TrevisanとPrasad Raghavendraで、審査委員会にはNikhil Srivastavaが加わった。博士論文の題名はApproximation and Hardness: Beyond P and NP（近似と困難さ：PとNPの向こう側）であり、その野心はタイトルに示されている。古典的な計算量理論は、問題を扱えるもの（P）と悪名高い難しいもの（NP完全）に分類する。Manurangsiの論文は、これらのカテゴリーがカバーしない領域を意図的に追求した。つまり、Pに属さず、NP困難であることも知られていない問題、例えばk-支配集合（k-dominating set）、k-クリーク（k-clique）、k-バイクリーク（k-biclique）、有向シュタイナーネットワーク、格子問題などであり、さらに直感に反して、最近傍ペアや最大内積のようにPの中に快適に収まっているにもかかわらず、高速な近似を拒絶する問題も含まれる。要旨によれば、この研究はパラメータ化計算量における2つの長年の未解決問題を解決し、いくつかの問題に対してこれまでで最高の非近似性を導き出したという。これは、境界線を越えるのではなく、境界線を引くことについての論文である。

最密k部分グラフの壁

彼の名声を確立した単一の結果は、最密k部分グラフ（Densest k-Subgraph）に関するものである。ネットワークが与えられたとき、接続が最も密集しているk個のノードを見つける問題である。Manurangsiは、指数時間仮説のもとでは、多項式時間アルゴリズムはnの1/(log log n)乗の定数倍よりも優れた近似比を達成できないことを証明した。また、より強力なGap-ETH仮説のもとでは、その障壁はf(n)がゼロに近づく任意の関数に対してn^f(n)にまで締め付けられる。これは多項式時間での困難さに極めて近い。決定的なのは、この構成が計算機科学で言う「完全な完全性（perfect completeness）」を持っていることである。これにより、k-クリークを真に含むグラフと、すべてのk部分グラフが疎であるグラフを区別できる。この論文は、計算機科学の理論における旗艦会議であるSTOC 2017で、Danny Lewin最優秀学生論文賞を受賞した。

Google、プライバシー、公正な分割

2019年7月以来、ManurangsiはGoogle Researchの研究科学者として勤務しており、アルゴリズムと理論、機械知能、不正対策の分野で100本以上の論文を発表している。関心の中心は、純粋な非近似性から、差分プライバシー、学習理論、計算社会選択（公正な分割、コンセンサス・ハービング、プライベートな順位集計、合成データ生成）へと移行している。最近の結果では、単調な効用を持つn人のエージェントに対して、O(√(n log n))個の財までのコンセンサス・ハービングが常に存在することが示され、以前の境界が改善された。受賞も相次いでおり、WAOA 2021での最優秀論文賞、ALT 2021での最優秀学生論文賞、FORC 2026での最優秀論文賞と佳作、IJCAI 2021および2023でのプログラム委員会賞、NeurIPS 2023でのトップ査読者ステータスを獲得している。

帰還の旅

2022年からはタイの国際情報オリンピック（IOI）チームおよび数学オリンピック合宿のコーチングチームに参加しており、2024年のIOIではタイ代表のゲスト団員を務めた。2023年からはCMKL大学の非常勤講師として、アルゴリズム、データ構造、プライバシー保護アルゴリズムを教えている。彼を生み出したパイプラインを、今では彼自身が運営を助けている。

Pasinが天才と呼ばれる理由

ここで問題となっている認知の質は非常に特異であり、単なる処理速度ではない。オリンピックの成功は、時間制限の下での迅速かつ正確な問題解決に報いるが、近似の困難さはその逆、すなわち、アルゴリズムの全クラスが運命にあることを証明するために精巧なリダクションを構築する忍耐力に報いる。Manurangsiは、その両方を高いレベルで行った稀有な存在であり、バークレーの論文がその証拠である。ほとんどの研究者が回避する領域を開拓したが、それは負の結果の方が発表が難しく、正解に辿り着くのが困難だからである。リダクションにおける一つの論理的ミスがすべてを無効にしてしまう。

誠実な反論は重要である。彼のホームページ、Google Researchのプロフィール、博士論文、当時のタイの報道を含め、手に入る記録の中で彼について「天才」という言葉を使っているものは一つもない。彼の受賞は会議委員会によるピアレビューに基づいた賞であり、歴史に残る天才ではなく、その場における最優秀論文を評価したものである。理論計算機科学はまた、絶え間なく協力的であり、彼の100本以上の論文は、共同執筆、セミナー、そしてこの分野の最強の計算量理論家二人が率いるバークレーのグループの産物である。彼のIOIの成績は優れているが、67位という順位も含まれている。誇張せずに言えることは、より狭く、かつ興味深いことである。彼は数学の中でも技術的に最も要求の厳しい隅々で活躍する一流のプロフェッショナルであり、その決定的な結果は長年未解決だった問題を解決した。それは天才であることとは別物であり、彼自身も一度も天才であることを主張したことはない。

展望

Manurangsiのキャリアは、理論家としては珍しい形をしている。最初は不可能性の証明であり、次は応用プライバシーの研究だった。差分プライバシーと公正な分割への移行は、壁がどこにあるかを確立した人間が、今度はその内側に構築することを望んでいることを示唆している。タイのオリンピックコーチングは、より永続的な遺産となるかもしれない。一度IOIを開催し、今ではそれを制する人々を育てている国があるということだ。