アヴィ・ウィグダーソン

アヴィ・ウィグダーソン（ヘブライ語: אבי ויגדרזון、1956年9月9日生まれ^{[ 1 ]}）は、イスラエルのコンピュータ科学者、数学者です。彼はアメリカ合衆国ニュージャージー州プリンストンにある高等研究所の数学科のハーバート・H・マース教授です。 ^{[ 2 ]}彼の研究分野は、計算複雑性理論、並列アルゴリズム、グラフ理論、暗号理論、分散コンピューティングなどです。^{[ 3 ]}ウィグダーソンは、理論計算機科学における業績により、2021年にアーベル賞を受賞しました。^{[ 4 ]}また、計算理論におけるランダム性の理解への貢献により、 2023年にチューリング賞を受賞しました。 ^{[ 5 ] [ 6 ]}

アヴィ・ウィグダーソンはイスラエルのハイファでホロコースト生存者の両親のもとに生まれた。^{[ 7 ]}ウィグダーソンはハイファのヘブライ語リアリ学校の卒業生である。彼は1977年にハイファのテクニオンで学部課程を開始し、1980年に卒業した。^{[ 8 ]}テクニオンで彼は妻のエドナと出会った。^{[ 8 ]}彼はプリンストン大学で大学院課程に進み、リチャード・リプトンの指導の下、「計算複雑性の研究」というタイトルの博士論文を完成させ、1983年にコンピュータサイエンスの博士号を取得した。^{[ 9 ] [ 10 ]}彼は計算複雑性の分野を大きく拡大した功績で知られている。^{[ 8 ]}

カリフォルニア大学バークレー校、カリフォルニア州サンノゼのIBMアルマデン研究所、バークレーの数理科学研究所で短期間勤務した後、イスラエルに戻り、1986年にヘブライ大学の教員となった。1987年に終身在職権を取得し、1991年に正教授となった。^{[ 8 ]} 1999年には高等研究所にも勤務し、2003年にはヘブライ大学の職を辞してIASに常駐するようになった。^{[ 3 ]}

ウィグダーソンは計算上の問題、特にその分野におけるランダム性の役割について調査した。ウィグダーソンはノーム・ニサンとラッセル・インパリアッツォと共に、コイン投げによって問題を解決するアルゴリズムについては、前提条件が満たされている限り、コイン投げを使用しないほぼ同等の速度のアルゴリズムが存在することを発見した。^{[ 8 ]}

ウィグダーソンは、オメル・レインゴールドとサリル・ヴァダンと共にジグザグ積を開発した。ジグザグ積は、計算複雑性理論、グラフ理論、群論を結びつけるものであり、例えば、迷路から抜け出す方法を理解するのに役立つ。^{[ 8 ]}現在、計算複雑性理論は暗号学で使用されている。^{[ 8 ]}

シルビオ・ミカリとオデッド・ゴールドライヒと共に、ウィグダーソンは、秘密データに関する公開結果を秘密裏に証明するためにゼロ知識証明を利用できることを実証した。^{[ 8 ]}

ウィグダーソンの息子、ユヴァル・ウィグダーソンはオーストリア科学技術研究所の数学教授である。^{[ 11 ]}

• 1994年：計算複雑性に関する研究でネヴァンリンナ賞を受賞。^{[ 12 ]}

• 2009年：グラフのジグザグ積に関する研究でゲーデル賞を受賞。これは、エキスパンダーグラフの構築に使用される、より小さなグラフを組み合わせてより大きなグラフを作成する方法である。^{[ 13 ]}

• 2011年：アメリカ芸術科学アカデミーの会員に選出される。^{[ 14 ]}

• 2018年：理論計算機科学と数学への貢献によりACMフェローに選出された。 ^{[ 15 ]}

• 2019年：ランダム化計算、暗号、回路複雑性、証明複雑性、並列計算、基本的なグラフ特性の理解など、コンピュータ科学の基礎への貢献に対してクヌース賞を受賞。 ^{[ 16 ]}

• 2021年：ラースロー・ロヴァースとアーベル賞を共同受賞。「理論計算機科学と離散数学への基礎的な貢献、そしてそれらを現代数学の中心分野へと形作る上での主導的な役割」が評価された。^{[ 17 ] [ 18 ] [ 19 ]}

• 2024年4月：Association for Computing Machineryよりチューリング賞を受賞。「計算におけるランダム性の役割に関する我々の理解を再構築し、理論計算機科学における数十年にわたる知的リーダーシップ」に対して。^{[ 5 ] [ 6 ]}
• 2025年：カーネギー財団ニューヨーク大移民賞^{[ 20 ]}

• アヴィ・ウィグダーソンのホームページ
• DBLP文献情報サーバーのAvi Wigderson氏