ズヴィ・ガリル

ズヴィ・ガリル
2023年のガリル
生まれる	( 1947-06-26 )1947年6月26日（77歳）[2] テルアビブ、パレスチナ委任統治領[2]
母校	テルアビブ大学( BSc、MSc ) コーネル大学(博士号)
受賞歴	ACMフェロー NAE会員 アメリカ芸術科学アカデミーフェロー
科学者としてのキャリア
フィールド	コンピュータサイエンス 数学
機関	IBM テルアビブ大学 コロンビア大学 ジョージア工科大学
博士課程の指導教員	ジョン・ホップクロフト[1]
博士課程の学生	モルデハイ・ベンアリ モティ・ユン デビッド・エップスタイン ジュゼッペ・F・イタリアーノ マシュー・K・フランクリン[1] ジョナサン・カッツ スチュアート・ハーバー

ズヴィ・ガリル（ヘブライ語：צביגליל、1947年6月26日生まれ）は、イスラエル系アメリカ人の コンピュータ科学者、数学者。2007年から2009年までコロンビア大学工学部の学部長、テルアビブ大学の学長を務めた。2010年から2019年まではジョージア工科大学計算機学部の学部長を務めた。^[3]

彼の研究対象は、アルゴリズムの設計と分析、計算の複雑さ、暗号化などです。彼は、ストリングロジーとスパース化という用語を作ったことで知られています。^{[4] [5]} 彼は200を超える科学論文を発表しており^{[6] 、} ISIの高引用研究者としてリストされています。^[7]

ガリルは1947年にパレスチナ委任統治領のテルアビブで生まれた。テルアビブ大学で応用数学の学士（1970年）と修士（1971年）をいずれも最優秀の成績で修了した。1975年にコーネル大学でコンピュータサイエンスの博士号を取得し、コーネル大学のコンピュータサイエンス教授ジョン・ホップクロフトの指導を受けた。^{[1]その後、}ニューヨーク州ヨークタウンハイツにあるIBMのトーマス・J・ワトソン研究所で博士研究員として1年間働いた。^[8]

1976年から1995年までテルアビブ大学のコンピュータサイエンス学部に勤務し、1979年から1982年まで学部長を務めた。1982年にコロンビア大学の教員となり、1989年から1994年までコンピュータサイエンス学部長を務めた。^{[2] [8]} 1995年から2007年までコロンビア大学傅財団工学・応用科学学部の学部長を務めた。^[9]この職に就いた際、同氏の名義で多額の寄付が寄せられたことを受けて、同氏は同校を中国人実業家の傅智英に敬意を表して命名する取り組みを監督した。^{[10]コロンビア大学では、1987年に}ジュリアン・クラレンス・レヴィ数学手法・コンピュータサイエンス教授に、1995年にはモリス・アンド・アルマ・A・シャピロ工学部長に任命された。 ^[2]

2007年、ガリルはイタマール・ラビノビッチの後任としてテルアビブ大学学長に就任した。^[11] 2009年、ガリルは辞職して教職員に復帰し、ジョセフ・クラフターが後任となった。^{[12] [13]} 2010年4月9日、ガリルはジョージア工科大学計算機科学部の学部長に任命された。 ^{[3]ジョージア工科大学では、}ユダシティ創設者のセバスチャン・スランとともに、ガリルは計算機科学部のオンライン修士課程（OMSCS）を考案し、同プログラムの教員による創設を主導した。^[14] OMSCSは、米国最大のオンライン修士課程となった。^{[15] OMSCSは、2013年の}ニューヨーク・タイムズの一面記事や、2021年のウォール・ストリート・ジャーナルとフォーブスのインタビューなど、数百の記事で取り上げられている。^{[14] [16] [17]} Inside Higher Educationは、OMSCSは「教育機関が大規模に高品質で低コストの学位を学生に提供できることを示唆している」と指摘した。^[18] The Chronicle of Higher Educationは、OMSCSは「学生が伝統的な学位に支払う金額を変える可能性が最も高いかもしれない」と指摘した。^[19] 2023年のForbesの記事「史上最高の学位プログラム」では、OMSCSは「ほぼあらゆる基準で、歴史上最も成功した学位プログラム」であると述べた。^[20]ガリルは2019年6月に学部長を辞任し、通常の教員の職に復帰した。^{[21] [22]}現在はジョージア工科大学でフレデリック・G・ストーリー・コンピューティング学部長およびオンラインプログラムのエグゼクティブアドバイザーを務めている。

1982年、ガリルはコロンビア大学理論の日を設立し、最初の15年間イベントを主催しました。このイベントは、現在もニューヨークエリア理論の日として存続しています。^{[23] 1983年から1987年まで、ガリルは}理論計算機科学の研究を推進する組織であるACM SIGACTの議長を務めました。^{[24]彼は1991年から1997年まで}SIAM Journal on Computingの編集長を務め、 1988年から2003年まで Journal of Algorithmsの編集長を務めました。

ガリルの研究分野はアルゴリズム、特に文字列、グラフ アルゴリズム、複雑性、暗号化です。また、ジャック キーファーとともに実験設計の研究も行っています。

ガリルのリアルタイムアルゴリズムは、文字列のマッチングと回文の認識において最速であり、最も基本的なコンピュータモデルであるマルチテープチューリングマシンでも動作します。より一般的には、彼は「予測可能性」条件を定式化し、それに準拠するオンラインアルゴリズムをリアルタイムアルゴリズムに変換できるようにしました。^{[25] [26]}ジョエル・セイフェラスとともに、ガリルは時間最適アルゴリズムを空間最適（対数空間）にも改良しました。^[27]

ガリルはダニー・ブレスラウアーと共同で、文字列照合のための線形作業O(loglogn)並列アルゴリズムを設計し^[28]、後に線形作業アルゴリズムの中で可能な限り最善の時間計算量を持つことを証明した。^[29]彼は他のコンピュータ科学者とともに、パターン前処理が与えられた場合に使用できる定数時間の線形作業ランダム検索アルゴリズムを設計した。^[30]

ガリルは学生たちとともに、正確または近似、順次または並列、1 次元または多次元の文字列マッチングのための、現在最も高速なアルゴリズムを 12 個以上設計しました。

ガリルは他のコンピュータ科学者と協力して、現在最も高速なグラフアルゴリズムをいくつか開発しました。例としては、最大重みマッチング、^[31]三価グラフ同型性、^[32]最小重みスパニングツリーなどがあります。^[33]

ガリルは学生たちとともに、「スパース化」^[34]と「スパース動的計画法」^{[35]と呼ばれる手法を考案した。前者は}動的グラフアルゴリズムの高速化に使用された。後者は文字列間のさまざまな編集距離の計算を高速化するために使用された。

1979年、ガリルはオフェル・ガッバーと共同で、明示的な拡張比を持つ拡張グラフの族を構築するというこれまで未解決であった問題を解決しました。 ^[36]これは高速グラフアルゴリズムの設計に役立ちます。

1995年、ガリルは「アルゴリズムの設計と分析への根本的な貢献と理論計算機科学コミュニティへの優れた貢献」により計算機協会のフェローに選出された^[37] 。また、2004年には「アルゴリズムの設計と分析への貢献と計算機科学と工学におけるリーダーシップ」により全米工学アカデミーに選出された^{[38] [39] 。}

2005年にアメリカ芸術科学アカデミーのフェローに選出された。^[40]

2008年、コロンビア大学は学生生活に対するズヴィ・ガリル賞を設立した。^[41] 2009年、コロンビア大学卒業生協会は彼にグレート・ティーチャー賞を授与した。^[42]

2012年、ウォータールー大学は、ガリルの「グラフアルゴリズムと文字列マッチングの分野における基礎的貢献」に対して名誉数学博士号を授与した。^[43] 2020年、アカデミック・インフルエンスは、ガリルを過去10年間で最も影響力のあるコンピューター科学者10人のリストに含め、ジョージア工科大学コンピューティング学部の諮問委員会は、130人以上の寄付者から200万ドル以上を集め、ガリルにちなんで名付けられた寄付講座を設立した。^{[44] [45]}

• ジョージア工科大学のホームページ