マヌエル・ブラム

マヌエル・ブラム（Manuel Blum、1938年4月26日 - ）はベネズエラのカラカス出身の計算機科学者。1995年、「計算複雑性理論の基礎的研究とその暗号およびプログラム検証への応用に関する貢献に対して」チューリング賞を授与された^[1]。

マヌエル・ブラム
マヌエル・ブラム(左)と妻子
生誕	(1938-04-26) 1938年4月26日（87歳） ベネズエラ カラカス
居住	アメリカ合衆国 ピッツバーグ
研究分野	計算機科学
研究機関	カリフォルニア大学バークレー校 カーネギーメロン大学
出身校	マサチューセッツ工科大学
博士課程 指導教員	マービン・ミンスキー
博士課程 指導学生	レオナルド・エーデルマン シャフィ・ゴールドワッサー ルイス・フォン・アン
主な受賞歴	チューリング賞(1995)
プロジェクト:人物伝

経歴

ブラムはマサチューセッツ工科大学で学び、1959年に学士号、1961年に修士号を取得（いずれも電気工学および計算機科学）。1964年にはマービン・ミンスキーの下で数学の博士号を取得した^[2]。1987年IEEEフェロー選出。

1999年までカリフォルニア大学バークレー校で計算機科学の教授を務めた^[3]。2002年、米国科学アカデミーの会員に選ばれた^[3]。

現在、ブラムはカーネギーメロン大学で計算機科学の教授を務めている。彼の妻 Lenore Blum と息子 Avrim Blum も同大学で計算機科学の教授を務めている。

業績

1960年代、ブラムは具体的なハードウェアからは独立した公理的な複雑性理論を生み出した。この理論はゲーデル数とブラムの公理に基づいている。具体的な機械モデルに基づいていないが、この理論から圧縮定理、ギャップ定理、honesty theorem、ブラムの加速定理などが生み出された。

他にも、電話によるコイン投げのためのプロトコル、線形時間の選択アルゴリズム、暗号論的に安全性が証明された擬似乱数生成法であるBlum-Blum-Shub、それとこの擬似乱数生成法をベースとした確率的公開鍵暗号であるBlum-Goldwasser暗号 (en)、Captchaなどの業績があげられる。

彼の指導学生は高確率で成功を収めている。レオナルド・エーデルマン、シャフィ・ゴールドワッサー、Russell Impagliazzo、シルビオ・ミカリ、Gary Miller、Moni Naor、Steven Rudich、マイケル・シプサ（英語版）、Umesh Vazirani、Vijay Vazirani、ルイス・フォン・アン、Ryan Williams など。

参考文献

• 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.