Manuel Blum
Professor EmeritusInfo Links
Research Areas
recursive function, cryptographic protocols, program checkingBiography
Manuel Blum is a pioneer in the field of theoretical computer science and the winner of the 1995 TuringAward in recognition of his contributions to the foundations of computational complexity theory and itsapplications to cryptography and program checking, a mathematical approach to writing programs thatcheck their work.He was born in Caracas, Venezuela, where his parents settled after fleeing Europe in the 1930s, andcame to the United States in the mid-1950s to study at the Massachusetts Institute of Technology. Whilestudying electrical engineering, he pursued his desire to understand thinking and brains by working in theneurophysiology laboratory of Dr. Warren S. McCulloch and Walter Pitts, then concentrated onmathematical logic and recursion theory for the insight it gave him on brains and thinking. He did hisdoctoral work under the supervision of Artificial Intelligence pioneer Marvin Minsky, and earned aPh.D. from MIT in mathematics in 1964.Blum began his teaching career at MIT as an assistant professor of mathematics and, in 1968, joined thefaculty of the University of California at Berkeley. He became the Bruce Nelson University Professor of Computer Science at Carnegie Mellon in 2001. Blum has supervised the theses of 35 doctoral students who now pepper almost every major computer science department in the country. The many ground-breaking areas of theoretical computer science chartered by his academic descendants are legend.Education
1964, Ph.D., Mathematics, MIT1961, M.S., Electrical Engineering, MIT
1959, B.S., Electrical Engineering, MIT
Selected Publications
L. von Ahn, M. Blum, and J. Langford, "Telling humans and computers apart automatically: How lazy cryptographers do AI," Communications of the ACM, vol. 47, no. 2, pp. 56-60, Feb. 2004.L. von Ahn, M. Blum, N. J. Hopper, and J. Langford, "CAPTCHA: Using hard AI problems for security," in Lecture Notes in Computer Science -- Advances in Cryptology, E. Biham, Ed., Vol. 2656, Berlin, Germany: Springer-Verlag, 2003, pp. 294-311.
H. Wasserman and M. Blum, "Software reliability via run-time result-checking," J. ACM, vol. 44, no. 6, pp. 826-849, Nov. 1997.
M. Blum and H. Wasserman, "Reflections on the Pentium division bug," IEEE Trans. Computers, vol. 45, no. 4, pp. 385-393, April 1996.
M. Blum, M. G. Luby, and R. A. Rubinfeld, "Self-testing/correcting with applications to numerical problems," in Proc. 22nd Annual ACM Symp. on Theory of Computing, H. Ortiz, Ed., New York, NY: ACM Press, 1990, pp. 73-83.
M. Blum and S. K. Kannan, "Designing programs that check their work," in Proc. 21st Annual ACM Symp. on Theory of Computing, D. S. Johnson, Ed., New York, NY: ACM Press, 1989, pp. 86-97.
M. Blum, P. Feldman, and S. Micali, "Non-interactive zero-knowledge and its applications (Extended abstract)," in Proc. 20th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 1988, pp. 103-112.
L. Blum, M. Blum, and M. Shub, "A simple unpredictable pseudo-random number generator," SIAM J. Computing, vol. 15, no. 2, pp. 364-383, May 1986.
M. Blum and S. Micali, "How to generate cryptographically strong sequences of pseudo-random bits," SIAM J. Computing, vol. 13, no. 4, pp. 850-864, Nov. 1984.
M. Blum, "Coin flipping by telephone -- A protocol for solving impossible problems," ACM SIGACT News, vol. 15, no. 1, pp. 23-27, Dec. 1983.
M. Blum, "How to exchange (secret) keys," ACM Trans. Computer Systems, vol. 1, no. 2, pp. 175-193, May 1983.
M. Blum and D. Kozen, "On the power of the compass (or, Why mazes are easier to search than graphs)," in Proc. 19th Annual Symp. on Foundations of Computer Science, New York, NY: IEEE, 1978, pp. 132-142.
L. Blum and M. Blum, "Toward a mathematical theory of inductive inference," Information and Control, vol. 28, no. 2, pp. 125-155, June 1975.
Awards, Memberships and Fellowships
Association for Computing Machinery (ACM) Fellow, 1999Diane S. McEntyre Award for Excellence in Teaching Computer Science, 1999
ACM A.M. Turing Award, 1995
Martin Meyerson Faculty Research Lecturer, 1995
American Academy of Arts and Sciences Member, 1995
Monie A. Ferst Award, 1991
American Association for the Advancement of Science (AAAS) Fellow, 1983
Institute of Electrical & Electronics Engineers (IEEE) Fellow, 1982
UC Berkeley Distinguished Teaching Award, 1977
Sloan Research Fellow, 1972