Luca Trevisanについて

Luca Trevisanが癌で52歳の若さで亡くなったという衝撃的なニュースが飛び込んできました.

Via Salil Vadhan: Luca Trevisan, a great complexity theorist, lost his battle with cancer today at the age of 52.

— Lance Fortnow (@fortnow) June 19, 2024

直接の面識は全くないのですが, 彼の多くの論文や結果, それにまつわる深い洞察は私の数学に重要な影響を与えており, 来週のSTOCでのワークショップでの彼の講演を直接見れるのをものすごく楽しみにしていただけに非常に残念に思います. STOCのワークショップでのスライドは準備されていたとのことですので, まさに「生涯現役」の研究者であるといえるでしょう. 理論計算機科学は世界的に非常に重要なリーダーの一人を喪失してしまいました.

彼の有名なブログ in theory は計算量理論, 加法的組合せ論, エクスパンダーグラフなど幅広い理論の最近の動向や手法を概説してくれるとても素晴らしいものであり, Terrence TaoのWhat's new や Boaz Barak の Windows On Theory などと並んで私のブログのスタイルに大きな影響を与えた存在でです.

計算量理論では, 例えばこちらのページのランダム抽出器の節で紹介した[Trevisan, 2001]や, こちらのページで紹介しているHardness vs. Randomnessに対して誤り訂正符号のlocal list-decodingに基づくアプローチを提案した[Sudan, Trevisan, Vadhan, 2001]が非常に有名です (もちろん, これに限らずもっと色々ありますが). また, Bogdanovと一緒に平均時計算量の非常に有名な教科書も執筆しています.

他にもスペクトルグラフ理論の文脈でよく知られるhigher-order Cheeger inequality (普通のCheeger不等式はグラフの頂点集合を二分割したときのカット辺の本数に関する不等式だが, higher-orderではグラフを$k$分割したときのカット辺の本数に着目する) の論文[Lee, Gharan, Trevisan, 2014]も有名です. この話はTrevisanによる解説記事があります.

また, 加法的組合せ論とその理論計算機科学への応用にまつわる様々な解説記事や講義ノート

• Guest column: additive combinatorics and theoretical computer science
• A mini course on additive combinatorics

も出しており, 私はこれらから加法的組合せ論の多くを学びました.

最近ではBecchettiらの研究グループでグラフ上の合意ダイナミクスと呼ばれるマルコフ連鎖やそれに基づくコミュニティ検出についての研究も精力的に行っており, 私の研究分野に非常に近い論文

• The Minority Dynamics and the Power of Synchronicity, Becchetti, Clementi, Pasquale, Trevisan, Vacus, Ziccardi, SODA24
• Stabilizing consensus with many opinions, Becchetti, Clementi,  Natale, Pasquale , Trevisan, SODA16
• Simple dynamics for plurality consensus, Becchetti , Clementi , Natale, Pasquale, Silvestri , Trevisan, SPAA14
• Find Your Place: Simple Distributed Algorithms for Community Detection, Becchetti, Clementi, Natale, Pasquale, Trevisan, SICOMP, 2020 (会議版はSODA2017)
• Average Whenever You Meet: Opportunistic Protocols for Community Detection, Becchetti, Clementi, Manurangsi, Natale, Pasquale, Raghavendra, Trevisan, ESA2018.

を出しており, その多くがSODAなどのトップ会議に採択されています.

私はTrevisanと直接交流したことはないのですが, 理論計算機科学の幅広い文脈でいつも見てよく資料で勉強させていただいた先生が若くして亡くなられたという事実に深い悲しみを覚え哀悼の意を捧げたいと思います.