マヌエル・ブラム
出典: フリー百科事典『ウィキペディア(Wikipedia)』
マヌエル・ブラム(Manuel Blum、1938年4月26日 - )はベネズエラのカラカス出身の著名な計算機科学者。1995年、「計算複雑性理論の基礎的研究とその暗号およびプログラム検証への応用に関する貢献に対して」チューリング賞を授与された。
目次 |
[編集] 経歴
ブラムはマサチューセッツ工科大学で学び、1959年に学士号、1961年に修士号を取得(いずれも電気工学)。1964年にはマービン・ミンスキーの下で数学の博士号を取得した。
1999年までカリフォルニア大学バークレー校で計算機科学の教授を務めた。[1].
現在、ブラムはカーネギーメロン大学で計算機科学の教授を務めている。彼の妻 Lenore Blum と息子 Avrim Blum も同大学で計算機科学の教授を務めている。
[編集] 業績
1960年代、ブラムは具体的なハードウェアからは独立した公理的な複雑性理論を生み出した。この理論はゲーデル数とブラムの公理に基づいている。具体的な機械モデルに基づいていないが、この理論から圧縮定理、ギャップ定理、honesty theorem、ブラムの加速定理などが生み出された。
他にも、電話によるコイン投げのためのプロトコル、線形時間の選択アルゴリズム、暗号論的に安全性が証明された擬似乱数生成法であるBlum-Blum-Shub、それとこの擬似乱数生成法をベースとした確率的公開鍵暗号であるBlum-Goldwasser暗号、Captchaなどの業績があげられる。
彼の指導学生は高確率で成功を収めている。レオナルド・エーデルマン、シャフィ・ゴールドワッサー、Russell Impagliazzo、シルビオ・ミカリ、Moni Naor、Steven Rudich、マイケル・シプサ、Umesh Vazirani、Vijay Vazirani など。
[編集] 参考文献
- M. Blum, "Coin flipping by telephone: a protocol for solving impossible problems", Proceedings of the 24th IEEE Computer Conference, pp133-137, 1982.
- Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
[編集] 外部リンク
ブラムのホームページ: