2023年ACMチューリング賞、Avi Wigderson教授に授与

 (awards.acm.org)
1 ポイント 投稿者 GN⁺ 2024-04-12 | 1件のコメント | WhatsAppで共有
  • ACMはAvi Wigdersonを2023年 ACM A.M. Turing Award の受賞者に選出し、計算理論と計算におけるランダム性の役割について新たな理解をもたらした功績を認めた
  • WigdersonはInstitute for Advanced StudyのHerbert H. Maass Professorであり、計算複雑性理論、アルゴリズム、暗号理論、並列・分散計算、組合せ論、グラフ理論を幅広く牽引してきた人物である
  • 中核的な業績はhardness for randomness研究で、広く信じられている計算上の仮定の下で、確率的多項式時間アルゴリズムを決定論的にシミュレーションできることを示した点にある
  • 関連論文は疑似乱数生成器、BPPの準指数時間シミュレーション、hardness-vs-randomnessのトレードオフを提示し、理論計算機科学の多くの領域に影響を与えた
  • Turing AwardはGoogleの支援により100万ドルの賞金が授与され、Wigdersonは技術的成果だけでなく若手研究者を導いたメンターとしても評価されている

ACMチューリング賞受賞の背景

  • ACMはAvi Wigdersonを2023年のACM A.M. Turing Award受賞者に選出した
  • 受賞理由は、計算理論への基礎的貢献、計算におけるランダム性の役割に対する理解を再構成した業績、そして理論計算機科学で数十年にわたり示してきた知的リーダーシップである
  • Wigdersonはニュージャージー州プリンストンのInstitute for Advanced Study数学部のHerbert H. Maass Professorである

  • 主な活動分野

    • 計算複雑性理論
    • アルゴリズムと最適化
    • ランダム性と暗号理論
    • 並列・分散計算
    • 組合せ論とグラフ理論
    • 理論計算機科学と数学・科学との接続
    • ACM A.M. Turing Awardは「コンピューティング界のノーベル賞」と呼ばれ、Google, Inc.の資金支援により100万ドルの賞金が提供される
    • この賞は、コンピューティングの数学的基礎を築いた英国の数学者Alan M. Turingの名にちなんで名付けられている

理論計算機科学が扱う問い

  • 理論計算機科学はコンピュータサイエンスの数学的土台を扱い、「この問題は計算で解けるのか」「解けるならどれだけの時間と資源が必要か」といった問いを扱う
  • この分野は効率的なアルゴリズム設計の原理も探究する
  • アルゴリズムは日常で使われるコンピューティング技術を可能にする基盤である
  • 理論計算機科学は、すぐに実用的応用を改善しない知的挑戦も扱うが、研究上のブレークスルーは多くの領域の発展につながり得る
    • 暗号理論
    • 計算生物学
    • ネットワーク設計
    • 機械学習
    • 量子コンピューティング

計算においてランダム性が重要な理由

  • コンピュータは本質的に決定論的システムであり、与えられた入力に対して、アルゴリズムの命令集合が計算と出力を一意に決定する
  • ランダム性とは、事象や結果に明確なパターンや予測可能性がない状態を指す
  • 現実世界には、気象システム、生物学的現象、量子現象のようにランダムに見える事象が多い
  • コンピュータ科学者たちは効率を高めるため、アルゴリズムが計算過程でランダムな選択を行うよう拡張してきた
  • 効率的な決定論的アルゴリズムが知られていなかった多くの問題も、小さな誤り確率を持つ確率的アルゴリズムによって効率的に解くことができる
    • この誤り確率は効率的に減らすことができる
  • 中核的な問いは、ランダム性が本質的か、取り除けるのか、そして確率的アルゴリズムの成功に必要なランダム性の質は何か、という点である
  • 計算におけるランダム性と疑似ランダム性の振る舞いをよりよく理解することは、より良いアルゴリズムの開発と、計算そのものの本質理解につながり得る

Wigdersonの中核的研究貢献

  • Wigdersonは40年にわたり理論計算機科学研究を牽引してきた人物であり、計算におけるランダム性と疑似ランダム性の役割を理解するうえで基礎的貢献を果たした
  • コンピュータ科学者たちは、ランダム性と計算の難しさ、すなわち効率的アルゴリズムを持たない自然な問題を特定することとの間に重要なつながりを見いだした
  • Wigdersonと共同研究者たちは、hardness for randomnessを扱う影響力ある研究を発表した
  • これらの研究は、標準的で広く信じられている計算上の仮定の下で、すべての確率的多項式時間アルゴリズムを効率的に決定論化できることを示した
  • この結果は、効率的計算にランダム性が必ずしも必要ではない可能性を示している
  • この研究の流れは、計算におけるランダム性の役割とランダム性に対する考え方を変えた

  • 代表的な論文3本

    • Hardness vs. Randomness
      • Noam Nisanとの共著
      • 新しいタイプの疑似乱数生成器を導入した
      • 従来よりはるかに弱い仮定の下で、ランダム化アルゴリズムの効率的な決定論的シミュレーションが可能であることを証明した
    • BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs
      • László Babai、Lance Fortnow、Noam Nisanとの共著
      • hardness amplificationを用いた
      • より弱い仮定の下で、bounded-error probabilistic polynomial time、すなわちBPPが無限に多くの入力長に対して準指数時間でシミュレーション可能であることを示した
    • P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
      • Russell Impagliazzoとの共著
      • より強力な疑似乱数生成器を導入した
      • ほぼ最適なhardness-vs-randomnessのトレードオフを提示した

影響範囲と追加の業績

  • Wigdersonの3本の論文は、ランダム性と決定論化の領域を超えて理論計算機科学の多くの分野に影響を与えた
  • これらの論文のアイデアは、その後多くの主要研究者による影響力ある論文で活用された
  • Omer Reingold、Salil Vadhan、Michael Capalboとの論文では、expander graphの最初の効率的な組合せ論的構成を提示した
    • expander graphは強い連結性を持つ疎グラフである
    • 数学と理論計算機科学の両方で重要な応用を持つ
  • ランダム性以外にも、Wigdersonは次の分野で知的リーダーシップを示してきた
    • multi-prover interactive proofs
    • 暗号理論
    • 回路複雑性

メンタリングと評価

  • Wigdersonは画期的な技術的貢献だけでなく、多くの若手研究者を指導した尊敬されるメンターであり同僚として認められている
  • 膨大な知識、技術的能力、親しみやすさ、情熱、寛大さは、優れた若手研究者が理論計算機科学のキャリアを志すよう導いた要因として挙げられている
  • ACM President Yannis Ioannidisは、Wigdersonが数学分野における生涯業績の最も重要な栄誉とみなされるAbel Prizeも受賞していると述べた
  • Ioannidisは、数学がコンピュータサイエンスの土台であり、Wigdersonの仕事がさまざまな数学の下位分野を理論計算機科学と結びつけたと評価した
  • Google Senior Vice President Jeff Deanは、Wigdersonのランダム性およびその他のテーマに関する研究が、過去30年にわたって理論計算機科学のアジェンダを設定してきたと述べた
  • Deanは、Wigdersonがアイデアと研究の方向性を生み出し、若手研究者がその方向で研究するよう動機づけたメンターでもあった点を強調した

Turing AwardとWigdersonの追加の主要論文

関連記事

1件のコメント

 
GN⁺ 2024-04-12
Hacker News のコメント

  • 発表で言及された Wigderson の主要論文 2 本は、有名なオンライン講義 From Nand to Tetris を作った教授の一人である Noam Nisan との共著

    • Nisan 教授もすごい人物。計算理論で一流の成果を上げた後、かなり異なる分野である アルゴリズム的ゲーム理論でも大きな影響を残した
      一人の人間がこれほど多様な成果を出せるという点も良いし、そうした柔軟性を許容したシステムも印象的
    • 本もある。最近 第2版 が出た

  • Quanta の良い記事もある: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Wigderson に取らせたポーズがいろいろあって面白かった。すごくぎこちなく見える。「さあ、この椅子に座って窓の外を物思いにふけるように見てください」みたいな感じ

    • 「ランダム性の不合理な有効性」が Wigderson にランダム性そのものの本質を考えさせた、というくだりが興味深い
      複雑性クラスは最悪の場合の性能を扱うものだと理解しているが、優れた疑似乱数生成器と優れたランダム化アルゴリズムがあっても、RNG + seed + problem instance のどんな組み合わせも指数時間を要しないことをどう証明するのか、概略を知りたい
    • 訂正文を見ると、元の記事では Wigderson が University of Haifa に通ったとしていたが、実際にはイスラエル・ハイファの Technion を卒業したとある
      記者がどうしてこれを混同したのか気になる
    • 「椅子に座って窓の外を見る」ポーズは Martin Scorsese や Sopranos 風のポーズみたい。老人ホームにいる年老いたギャングのような場面

  • Scott Aaronson が、Avi Wigderson のある講演が自分の進路にどのような影響を与えたかを書いた記事がある: https://scottaaronson.blog/?p=2925

  • “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness” に追加情報がある: [1] および保存版 [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Wigderson の研究のうち、困難性とランダム性のトレードオフの方面を追うには、どこから始めるのがよいのか気になる
    Turing 賞受賞者の名前をまったく聞いたことがないというのは珍しいが、この人は完全に視野の外にいた

    • 彼の本を読めばいい: https://www.math.ias.edu/avi/book
    • 「標準的で広く信じられている計算上の仮定」が何なのか気になる
      おそらく NP完全問題 に対する確率的近似も多項式時間ではない、という意味なのかと思うが、あるいはランダム性を取り除いた版もなお近似アルゴリズムだという意味なのか、混乱している

  • Wigderson の本をちょうど手に取ったところだが、今のところ気に入っている: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • 個人の研究や教育目的なら、本の最終ドラフトをここで見られる: https://www.math.ias.edu/avi/book
    • 本を見たが、大学院生か上級学部生向けのレベルに見える
      コンピュータサイエンス／数学の学部レベルの背景知識が少しさびついている人に、計算のトピックをもっと基礎から扱う本を勧めてもらえるか気になる

  • 関連記事にこういう文がある: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    「ある命題が証明可能なら、それはゼロ知識証明も持つ」なんて、頭が爆発しそうな感じ
    さらに「ランダムビットの代わりに疑似乱数ビットを確率的アルゴリズムに入れると、同じ問題に対する効率的な決定的アルゴリズムになる」というのも、とんでもなく驚き
    AI も確率的計算なのだから、もし自分が正しく読めているなら、現在のモデルの複雑さを何桁も減らせるという意味ではないかと思う。初心者の勘違いなら誰か引き戻してほしい

    • 正確に何を意味しているのかは分からないが、少なくともそういう意味ではない。AI はすでに疑似乱数を使っており決定的
      効率を上げるためにアナログ計算を使う特殊な AI アクセラレータチップのような例外はある
    • 残念ながら違う。第一に、その結果は探索問題ではなく決定問題に適用される
      第二に、作られる決定的アルゴリズムはランダム化アルゴリズムよりはるかに非効率。ただし弱い仮定の下で同じ複雑性クラスに属するだけ

  • 記事のこの部分が良かった: 「応用が動機ではないが、基礎研究でも使い道を見いだせることは分かっている。Alan Turing を考えてみてほしい。彼は Entscheidungsproblem に関する論理学・数学の論文を、あまり知られていないジャーナルに書いた。応用が動機ではなかった」
    Feynman の皿の逸話と似ている。大学の食堂で見たものに軽く反応したことから始まり、最終的に Nobel賞 につながった
    要点をさらに広げれば、現代の学界はまさにこうした好奇心駆動の探究を抑え込む方向に向かっている

  • ACM によると、Avi Wigderson は計算におけるランダム性の役割の理解を作り替えるなど、計算理論に基礎的な貢献をし、理論計算機科学で数十年にわたる知的リーダーシップを示したことから、2023 ACM A.M. Turing Award の受賞者に選ばれた
    Wigderson はニュージャージー州プリンストンの Institute for Advanced Study 数学部の Herbert H. Maass Professor であり、計算複雑性理論、アルゴリズムと最適化、ランダム性と暗号、並列・分散計算、組合せ論、グラフ理論、理論計算機科学と数学・科学のつながりなどで中心的な人物として活動してきた
    2021年に Abel賞 も受賞しており、理論／抽象数学とコンピュータサイエンスの最高栄誉をともに受けた、かなり珍しい組み合わせとなった

    • 理論計算機科学と数学の重なりは、たいていの人が知っているよりはるかに大きい
      簡単な例として MIT の理論計算機科学の科目一覧 https://catalog.mit.edu/subjects/6/ を見ると、どれほど多くの科目が数学である course 18 と共同開講されているか確認できる
    • 厳密に言えば、数学の最高栄誉は Fields Medal
      もちろん、自分がどうこう言える立場ではないが

  • 確率／ランダム性と計算 をテーマに、初級者にやさしいものから上級まで、学習に使える資料のおすすめが気になる
    Google では Eli Upfal と Michael Mitzenmacher の “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” が出てくるが、初級／入門向けの本・記事・動画がなかなか見つからない