2023年のチューリング賞が発表されました！コンピュータの「ランダム性」はなぜそれほど重要なのでしょうか?

昨夜、米国計算機協会（ACM）は、コンピューティングにおけるランダム性の役割についての理解を再構築するなど計算理論への基礎的な貢献と、理論計算機科学の分野での数十年にわたるリーダーシップを認められ、2023年のACM AMチューリング賞を数学者でありトップクラスの理論計算機科学者であるアヴィ・ウィグダーソンに授与すると発表しました。

ACM AM チューリング賞は、コンピュータ業界に重要な貢献をした個人を表彰するために ACM によって 1966 年に設立されました。チューリング賞は、英国の科学者でありコンピューター科学の先駆者であるアラン・M・チューリングにちなんで名付けられました。この賞を設立した目的の一つは、この偉大な科学者を記念することです。

チューリング賞は受賞者に極めて高い要件を課し、非常に厳格な審査プロセスを採用しています。通常、毎年 1 人のコンピューター科学者のみが受賞し、同じ方向に貢献した 2 人の科学者が同時に受賞するのは非常にまれな年のみです。そのため、チューリング賞はコンピュータ業界で最も権威があり、高貴な賞でもあり、「コンピュータ業界のノーベル賞」として知られています。

理論計算機科学とは何ですか?

理論計算機科学は、この分野の数学的基礎を扱います。 「この問題は計算的に解決可能か？」といった質問をします。または「この問題が計算によって解決できる場合、どれくらいの時間とその他のリソースが必要になりますか？」理論計算機科学では、効率的なアルゴリズムの設計についても研究します。

私たちの生活に密接に関係するあらゆるコンピューティング技術は、アルゴリズムを通じて実装されています。強力で効率的なアルゴリズムがどのように機能するかを理解することで、コンピューター サイエンスだけでなく、自然の法則に対する理解も深まります。理論計算機科学における研究の進歩は、暗号学や計算生物学からネットワーク設計、機械学習、量子コンピューティングに至るまで、この分野のほぼすべての分野で進歩をもたらしました。

ランダム性はなぜ重要なのでしょうか?

コンピュータは基本的に決定論的なシステムです。任意の入力に適用されたアルゴリズム命令のセットは、その計算、特にその出力を一意に決定します。言い換えれば、決定論的アルゴリズムは予測可能なパターンに従います。対照的に、ランダム性には明確なパターンがなく、出来事や結果の予測可能性もありません。私たちが住む世界は気象システム、生物学的現象、量子現象などのランダムな出来事で満ちているため、コンピューター科学者は計算中にランダムな選択を行えるようにアルゴリズムを強化し、それによって効率を向上させてきました。実際、効率的な決定論的アルゴリズムが知られていない多くの問題は、多少のエラーの確率はあるものの（これは効果的に低減できる）、確率的アルゴリズムを使用して効率的に解決されてきました。

しかし、ランダム性は不可欠なのでしょうか、それとも排除できるのでしょうか?確率的アルゴリズムが成功するために必要なランダム性の質はどうでしょうか?これらおよびその他の多くの基本的な質問は、コンピューティングにおけるランダム性と疑似ランダム性を理解するための鍵となります。計算における確率のダイナミクスをより深く理解することで、より優れたアルゴリズムを開発し、計算自体の性質についての理解を深めることができます。

ウィグダーソンの貢献

ウィグダーソン氏は、計算複雑性理論、アルゴリズムと最適化、ランダム性と暗号化、並列および分散コンピューティング、組合せ論、グラフ理論、および理論計算機科学と数学と科学のつながりの分野でリーダー的存在です。

ウィグダーソン氏は 40 年にわたり、コンピューター サイエンスの理論研究の第一人者として活躍し、コンピューティングにおけるランダム性と疑似ランダム性の役割の理解に基礎的な貢献をしてきました。

コンピューター科学者は、ランダム性と計算の難しさ（つまり、効率的なアルゴリズムが存在しない自然の問題を特定すること）の間に驚くべき関連性があることを発見しました。ウィグダーソン氏は同僚と共同で、ランダム性と難しさの交換に関する影響力のある一連の本を執筆した。彼らは、標準的で広く信じられている計算上の仮定の下では、あらゆる確率的多項式時間アルゴリズムを効率的に非ランダム化できる（つまり、完全に決定論的にできる）ことを示しています。

言い換えれば、ランダム性は効率的なコンピューティングに必要な条件ではありません。この一連の研究は、コンピューティングにおけるランダム性の役割についての理解に革命をもたらし、ランダム性についての考え方を変えました。これらの影響力のある論文には次の 3 つが含まれます。

1) 「Hardness vs. Randomness」（Noam Nisan との共著）。この論文では、他の研究結果の中でも、新しいタイプの疑似乱数ジェネレーターを紹介し、これまで知られていたよりも弱い仮定の下で、ランダム化アルゴリズムの効率的な決定論的シミュレーションが可能であることを示しています。

論文リンク: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2) 「EXPTIME に公開可能な証明がない限り、BPP は準指数時間シミュレーションを実行できます」(László Babai、Lance Fortnow、Noam Nisan との共著) この論文では、「困難性増幅」を使用して、より弱い仮定の下では、制限されたエラー確率多項式時間 (BPP) を無限の入力長に対して準指数時間でシミュレートできることを証明しています。

論文リンク: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3) 「E に指数回路が必要な場合、P = BPP: XOR 補題の非ランダム化」(Russell Impagliazzo との共著) この論文では、困難性とランダム性の間でほぼ最適なトレードオフを実現する、より強力な疑似ランダム生成器を紹介しています。

論文リンク: https://dl.acm.org/doi/pdf/10.1145/258533.258590

重要なのは、これら 3 つの論文の影響が、ランダム性と非ランダム化の分野をはるかに超えていることです。これらの論文のアイデアは、後に理論計算機科学の多くの分野に応用され、この分野の多くの第一人者による影響力のある論文につながりました。その後、ウィグダーソンは、依然として計算ランダム性の広範な分野で研究を続け、オマー・ラインゴールド、サリル・ヴァダン、マイケル・カパルボと共同研究を行い、別の論文で、強い連結性を持つ疎グラフである拡張グラフの効率的な組み合わせ構築を初めて提案しました。これらは、数学と理論計算機科学の両方において多くの重要な応用があります。

論文リンク: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

ウィグダーソン氏は、ランダム性に関する研究に加え、マルチ検証対話型証明、暗号化、回路の複雑性など、理論計算機科学のいくつかの分野のリーダーでもあります。

尊敬する指導者

ウィグダーソン氏は、画期的な技術的貢献に加え、数え切れないほどの若い研究者にアドバイスを与え、尊敬される指導者、同僚として認められました。彼の幅広い知識と優れた技術的スキル、そして親しみやすさ、熱意、寛大さが相まって、多くの優秀な若者を理論計算機科学の分野に惹きつけることができました。

「アヴィ・ウィグダーソン氏が、数学における生涯の功績に対する最も重要な栄誉とされるアーベル賞も受賞したことは特筆すべきことだ」とACMのヤニス・イオアニディス会長は述べた。 「アヴィ・ウィグダーソン氏のランダム性やその他のテーマに関する研究は、過去30年間にわたり理論計算機科学の方向性を定めてきました」と、Googleの研究担当上級副社長ジェフ・ディーン氏は説明する。 「コンピューターサイエンスの初期の頃から、研究者はランダム性が幅広いアプリケーションのためのより高速なアルゴリズムを設計する方法であることを認識してきました。ランダム性をより深く理解するための努力は私たちの分野に重要な利益をもたらし続けており、ウィグダーソンはこの分野で新境地を切り開きました。」

ウィグダーソンの経歴

ウィグダーソン氏は 1999 年以来、プリンストン高等研究所のハーバート H. マース数学教授を務めています。彼は以前、エルサレムのヘブライ大学の教授を務め、プリンストン大学、カリフォルニア大学バークレー校、IBM などの機関で客員教授を務めていました。

ウィグダーソン氏はイスラエル工科大学テクニオン校を卒業し、プリンストン大学でコンピュータサイエンスの修士号、修士号、博士号を取得しました。受賞した賞には、アーベル賞、IMU アバカス賞、ドナルド・E・クヌース賞、分散コンピューティングにおけるエドガー・W・ダイクストラ賞、ゲーデル賞などがあります。彼は ACM、米国科学アカデミー、アメリカ芸術科学アカデミーの会員です。

参考リンク: https://awards.acm.org/about/2023-turing