アヴィ・ヴィグダーソン（ヘブライ語: אבי ויגדרזון、1956年9月9日生まれ）は、イスラエルの計算機科学者であり数学者である。彼は、アメリカ合衆国ニュージャージー州プリンストンにある高等研究所の数学部門でハーバート・H・マース教授を務めている。彼の研究関心は、計算複雑性理論、並列アルゴリズム、グラフ理論、暗号理論、分散計算に及ぶ。ヴィグダーソンは、理論計算機科学における変革的な業績により、2021年にアベル賞、2023年にチューリング賞を受賞した。
ヴィグダーソンの研究は、計算におけるランダム性の役割と効率的なアルゴリズムの構造に焦点を当てている。彼は複雑性理論の第一人者であり、ランダム化アルゴリズムの威力の理解、ジグザグ積による展開グラフの構築、ゼロ知識証明の基礎への重要な貢献を行っている。
幼少期と教育
ヴィグダーソンは、1956年9月9日にイスラエルのハイファで、ホロコースト生存者の両親のもとに生まれた。彼はハイファのヘブライ・レアリ学校に通った。1977年、彼はテクニオン工科大学で学部課程を開始し、1980年に卒業した。テクニオンで、彼は妻のエドナと出会った。その後、彼はプリンストン大学で大学院研究を進め、1983年に計算機科学の博士号を取得した。彼の博士論文「計算複雑性の研究」は、リチャード・リプトンの指導の下で執筆された。ヴィグダーソンは、計算複雑性の分野を大幅に豊かにしたと評価されている。
学術経歴
カリフォルニア大学バークレー校、カリフォルニア州サンノゼのIBMアルマデン研究所、バークレーの数理科学研究所での短期職を経て、ヴィグダーソンは1986年にイスラエルに戻り、ヘブライ大学エルサレム校の教員となった。彼は1987年に終身在職権を取得し、1991年に正教授となった。1999年には高等研究所のポストにも就き、2003年にはヘブライ大学の職を辞して、プリンストン研究所のハーバート・H・マース教授の役割を引き受けた。
高等研究所では、ヴィグダーソンは計算複雑性、数学、暗号理論の間の相互作用に焦点を当ててきた。彼はこれらの分野の研究者の世代を指導してきた。
主な貢献
ヴィグダーソンは、効率的な計算にランダム性が必要かどうかという根本的な問いを調査した。ノアム・ニサンおよびラッセル・インパリアッツォとともに、ヴィグダーソンは、特定の条件下でランダムなコイン投げに依存するアルゴリズムに対して、ランダム性を使用しないほぼ同速の決定論的アルゴリズムが存在することを示した。この研究の流れは、擬似ランダム性の概念に基づいており、理論計算機科学の基盤である。
オメール・ラインゴールドおよびサリル・ヴァダンとともに、ヴィグダーソンはジグザグ積を開発した。これは、小さなグラフを組み合わせて、より大きくて接続性の高いグラフを生成するグラフ上の組み合わせ操作である。この概念は複雑性理論、グラフ理論、群理論を橋渡しし、迷路のナビゲーションの理解から効率的な展開グラフの構築まで、さまざまな応用がある。ジグザグ積は理論計算機科学における主要なツールとなった。
ヴィグダーソンは、シルビオ・ミカリおよびオデッド・ゴールドライヒとともに、ゼロ知識証明を使用して、秘密データに関する公開結果を、基礎となる秘密を明かさずに検証できることを示した。この業績は、現代暗号理論の基盤層である。
受賞と栄誉
ヴィグダーソンは、計算複雑性に関する業績により、1994年に国際数学連合のネヴァンリンナ賞を受賞した。2009年には、ジグザグ積によるグラフ構築でゲーデル賞を共有した。彼は2011年にアメリカ芸術科学アカデミーの会員に選出され、2018年には理論計算機科学への貢献によりACMフェローに選出された。
2019年、ヴィグダーソンは、ランダム化計算、回路複雑性、証明複雑性、並列計算に関する研究などにより、クヌース賞を受賞した。彼は、理論計算機科学と離散数学への基礎的な貢献により、ラズロ・ロバースとともに2021年にアベル賞を受賞した。2024年4月、計算機科学協会は、ランダム性の理解を再形成し、理論計算機科学における長年のリーダーシップに対して、彼にチューリング賞を授与した。また、彼は2025年にカーネギー・コーポレーションのグレート・イミグラント賞も授与された。
個人生活
ヴィグダーソンはエドナと結婚しており、息子のユバルがいる。ユバルはオーストリア科学技術研究所の数学教授である。ヴィグダーソンは、自身の研究と指導を通じて、次世代の研究者に影響を与え続けている。