マイケル・O・ラビン

ラビンは1931年、ドイツ、プロイセン、下シレジア地方のブレスラウ（現在のポーランド、ヴロツワフ）で、ラビの息子として生まれた。1935年、家族とともにイギリス委任統治領パレスチナに移住した。幼い頃から数学に強い関心を持っていた彼は、父親の勧めでハイファの最高の高校に入学し、当時高校教師だった数学者のエリシャ・ネタニヤフに師事した。 ^{[ 1 ]}

彼は1948年にハイファのヘブライ語リアリ学校を卒業し、 1948年の第一次中東戦争中に徴兵された。エルサレムで数学教授をしていた数学者のアブラハム・フランケルが軍司令部に働きかけ、ラビンは1949年に除隊して大学で学ぶことになった。 ^{[ 1 ]}その後、エルサレムのヘブライ大学で理学修士号を取得した。ペンシルベニア大学で大学院課程を開始し、 1956年にプリンストン大学で博士号を取得した。^{[ 2 ]}

1950年代後半、ラビンはIBMの夏期研究員としてニューヨーク州ウェストチェスター郡のラム・エステートに招かれ、他の有望な数学者や科学者たちと共に研究を行った。そこで彼はダナ・スコットと共に「有限オートマトンとその決定問題」という論文を執筆した。^{[ 3 ]}その後、非決定性オートマトンを用いて、有限状態機械が正規言語を正確に受理するというクリーネの結果を再証明することに成功した。^{[ 1 ]}

計算複雑性理論の起源については、翌年の夏、ラビンはラム・エステートに戻った。ジョン・マッカーシーはスパイ、警備員、パスワードに関するパズルを彼に提示し、ラビンはそれを研究し、その後すぐに「関数の計算の難易度と再帰的集合の階層」という論文を書いた。^{[ 1 ] [ 4 ]}

非決定性マシンは、特に複雑性クラスPとNPの記述によって、計算複雑性理論における重要な概念となった。

その後、彼はエルサレムに戻り、論理学を研究し、後にコンピュータ科学として知られるようになる分野の基礎に取り組んだ。彼は29歳でヘブライ大学の准教授兼数学研究所所長となり、33歳で正教授となった。ラビンは当時を振り返り、「計算の問題に関する私の研究は全く評価されていなかった。数学者たちは、新たに出現した分野を認識していなかった」と述べている。^{[ 1 ]}

1960年、ラビンはエドワード・F・ムーアに招かれてベル研究所で働き、そこでコイン投げを使ってどの状態遷移を取るかを決定する確率オートマトンを導入した。彼は、非常に多くの状態を必要とする正規言語の例を示したが、確率オートマトンを使うと状態数が指数関数的に減少することがわかった。^{[ 1 ]}

ラビンは、1961年から1962年の学年度にカリフォルニア大学バークレー校で、 1962年から1963年の学年度にMITで数学の客員准教授を務めた。1981年にハーバード大学のゴードン・マッケイ・コンピュータ科学教授に就任する前は、ヘブライ大学の教授であった。^{[ 5 ]}

1966年（1967年の会議議事録に掲載）に、^{[ 6 ]}ラビンは多項式時間の概念を導入しました（これは、コブハム^{[ 7 ]}とエドモンズ^{[ 8 ]}によって独立して、ごく最近導入されたものです）。

1969年、ラビンは無限木オートマトンを導入し、n個の後継者（n =2の場合はS2S ）の単項2階理論が決定可能であることを証明した。^{[ 9 ]}この証明の重要な要素は、ボレル階層の第3レベルにあるパリティゲームの決定性を暗黙のうちに示した。

1975年、ラビンはエルサレム・ヘブライ大学の学長としての任期を終え、客員教授としてアメリカのマサチューセッツ工科大学に赴任した。そこでラビンは、ある数が素数かどうかを非常に速く（ただし、わずかな誤り確率で）判定できるランダム化アルゴリズムであるミラー・ラビン素数判定法を発明した。^{[ 10 ] [ 11 ]}ラビンの方法は、一般化リーマン予想が真であるという仮定のもとで決定論的に問題を解決したゲイリー・ミラーの以前の研究に基づいていたが、ラビンのバージョンの判定法はそのような仮定を置かなかった。高速素数判定は、ほとんどの公開鍵暗号の実装の成功に不可欠であり、2003年にミラー、ラビン、ロバート・M・ソロベイ、フォルカー・シュトラッセンは、素数判定に関する業績によりパリ・カネラキス賞を受賞した。

1976年、ラビンはジョセフ・トラウブに招かれ、カーネギーメロン大学で会合を開き、トラウブが「革命的」と呼んだ素因数判定法を発表した。^{[ 1 ]}

1978年、ラビンはラビン署名アルゴリズムを発明した。これは、その安全性が整数因数分解の難解さと同等であることが証明された最初の非対称暗号システムである。^{[ 12 ] [ 13 ]}

1981年、ラビンはウィーズナーが考案したオブリビアス転送技術の弱い変種を多重化という名称で再発明し、^{[ 14 ]}送信者が受信者にメッセージを送信すると、受信者は0から1の間の確率でメッセージを学習することができ、送信者は受信者がメッセージを学習できたかどうかを知ることができない。

1987年、ラビンはリチャード・カープと共に、最もよく知られた効率的な文字列検索アルゴリズムの1つであるラビン・カープ文字列検索アルゴリズムを開発した。このアルゴリズムはローリングハッシュで知られている。^{[ 15 ]}

ラビン氏のその後の研究は、コンピュータセキュリティに集中した。2007年春学期には、コロンビア大学の客員教授として暗号学入門を教えた。ハーバード大学のトーマス・J・ワトソン・シニア名誉コンピュータサイエンス教授、およびヘブライ大学の名誉コンピュータサイエンス教授として、常勤の学術生活から引退した。

ラビンは2026年4月14日に94歳で死去した。^{[ 16 ]}

彼の娘であるタル・ラビンも著名なコンピュータ科学者である。^{[ 17 ]}