「計算機科学のノーベル賞」ことチューリング賞の2023年度受賞者が計算のランダム性の理解に貢献したアヴィ・ヴィグダーソン氏に決定

by Institute for Advanced Study

計算機科学分野で優れた業績を残した人物に与えられるチューリング賞の2023年度受賞者に、イスラエル出身でプリンストン高等研究所の計算機科学者であるアヴィ・ヴィグダーソン氏が選ばれました。ヴィグダーソン氏は、「計算におけるランダム性の理解の再構築」および「理論コンピューターサイエンスにおける数十年にわたる知的リーダーシップ」が認められたとのことです。

2023 Turing Award
https://awards.acm.org/about/2023-turing

Grad alum Avi Wigderson wins Turing Award for 'groundbreaking insights' in computer science
https://www.princeton.edu/news/2024/04/10/grad-alum-avi-wigderson-wins-turing-award-groundbreaking-insights-computer-science

Computer scientist wins Turing Award for seminal work on randomness | Ars Technica
https://arstechnica.com/science/2024/04/computer-scientist-wins-turing-award-for-seminal-work-on-randomness/

For Turing Award winner, everything is computation and some problems are unsolvable | ZDNET
https://www.zdnet.com/article/for-turing-award-winner-everything-is-computation-and-some-problems-are-unsolvable/

計算機科学分野の国際学会であるAssociation for Computing Machinery(ACM)は2024年4月10日、2023年度のチューリング賞をプリンストン研究所のヴィグダーソン氏に授与することを決定しました。チューリング賞は、電子計算機の黎明(れいめい)期に重要な貢献を果たしたアラン・チューリングにちなんで名付けられ、「計算機科学のノーベル賞」とも呼ばれる名誉ある賞であり、受賞者にはGoogleの後援で100万ドル(約1億5000万円)が贈呈されます。

ヴィグダーソン氏は1956年にイスラエルのハイファで、電子技師と看護師の息子として生まれました。イスラエル工科大学で学士号を得たヴィグダーソン氏はアメリカのプリンストン大学に進学し、1983年にコンピューターサイエンスの博士号を取得。記事作成時点ではプリンストン高等研究所で数学教授を務めています。

ヴィグダーソン氏は海外メディアのZDNetのインタビューに対し、「計算は本当に基本的な概念です。コンピューターのアルゴリズムだけでなく、あらゆるものが計算しているのです」と述べ、貝殻の模様から胚の成長、シロアリによるアリ塚の建設、さらにゴシップの拡散に至るまでさまざまな現象は計算だと主張。「誰かに教えられたりFacebookで見たものを話す時など、情報がどのように進化していくのかは完全な計算モデルで組み立てられる計算問題なのです」と述べています。

今回、ヴィグダーソン氏にチューリング賞が授与された理由のひとつが、コンピューターの計算におけるランダム性についての理解を再構築したという点です。コンピューターは基本的に決定論的なシステムですが、1970年代の研究者らは計算中にあえてランダムな選択をさせることで、結果的にアルゴリズムの効率を向上させられることを発見しました。そのため、コンピューター科学者らは決定論的なアルゴリズムのランダム化バージョン(確率的アルゴリズム)から始め、それを非ランダム化することで決定論的なアルゴリズムを取得していたとのこと。

ところがヴィグダーソン氏は1994年に発表した論文で、「効率的な確率的アルゴリズムはすべて決定論的アルゴリズムに置き換えることが可能であり、効率的な計算のためにランダム性が必要ない」ことを証明しました。その後に続いた2つの論文でも、ランダム性に関する研究をさらに拡張しました。

ヴィグダーソン氏は、「問題はアルゴリズムのランダム性がどれほど強力なのかという点でした。これらの論文は、ランダム性がそれほど強力ではないことを示すのを目的としていました。これらの論文ではすべて、難しい問題を取り上げてランダムに見えるビットを決定論的に生成する疑似ランダム生成器を作り、確率論的アルゴリズムのランダムな入力を置き換えることで決定論的なアルゴリズムを作っています」と述べています。

これらの論文のアイデアは、理論的なコンピューターサイエンスの分野に大きな影響を与え、応用研究者らによって実際のソフトウェアにも活用されています。ACMは、「この一連の作業は、計算におけるランダム性の役割と、ランダム性についての私たちの理解に革命をもたらしました」と述べて高く評価しました。

また、ヴィグダーソン氏は画期的な技術的貢献に加え、多くの若い研究者に助言を与えるメンターとしても尊敬を集めているとのこと。ACMは「彼の膨大な知識と比類のない技術的熟練度は、彼の親しみやすさ、熱意、寛大さと相まって、理論的なコンピューターサイエンスのキャリアを追求する多くの最高の若者を魅了しています」と述べ、これらの理由でヴィグダーソン氏にチューリング賞を授与したと報告しました。