Manuel Blum (born 26 April 1938 in Caracas, Venezuela) is a computer
scientist who received the Turing
Award in 1995 "In recognition of his contributions to the
foundations of computational complexity
theory and its application to cryptography and program
checking".
Biography
Blum
attended MIT, where he received his bachelor's degree and his master's degree in EECS in 1959 and 1961
respectively, and his Ph.D. in
Mathematics in 1964 under professor
Marvin Minsky.
He worked
as a professor of computer science at the University of
California, Berkeley until 1999 [39056].
He is
currently the Bruce Nelson Professor of Computer Science at
Carnegie Mellon
University, where his wife, Lenore
Blum, and son, Avrim Blum, are also
professors of Computer Science.
Work
In the 60s he developed an axiomatic complexity theory which was
independent of concrete machine models. The theory is based on
GĂ¶del numberings and the
Blum axioms. Even though the theory is
not based on any machine model it yields concrete results like the
compression theorem, the
gap theorem, the
honesty theorem and the celebrated
Blum speedup theorem.
Some of his other work includes a protocol for
flipping a coin over a telephone, a linear
time
Selection algorithm, the
Blum Blum Shub pseudorandom number
generator, the
Blum-Goldwasser cryptosystem,
and more recently
CAPTCHA.
His PhD Advisees, with unusual frequency, have gone on to very
distinguished careers. Among them are
Leonard Adleman,
Shafi Goldwasser,
Russell Impagliazzo,
Silvio Micali,
Gary Miller,
Moni Naor,
Steven
Rudich,
Michael Sipser,
Umesh and
Vijay
Vazirani,
Luis von Ahn,
Ryan Williams and
Ivan da Costa Marques.
See also
External links
Blum's home pages: