2024年6月20日木曜日

Luca Trevisanについて

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


直接の面識は全くないのですが, 彼の多くの論文や結果, それにまつわる深い洞察は私の数学に重要な影響を与えており, 来週の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による解説記事があります.

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

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

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

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

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


時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)

講義資料をNotionで書いてみた

 プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました. 講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどう...

  • ランダムグラフ入門
    0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます.  1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ...
  • 駆け足で学ぶ「グラフマイナー定理」
    0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで...
  • 高速な全点対最短経路アルゴリズム
    1. 全点対最短経路問題の計算量の外観 　グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...