Manuel Blum

Manuel Blum ( born April 26, 1938 in Caracas, Venezuela) is an American computer scientist who was awarded in 1995 " in recognition of his contributions to the foundations of computational complexity theory and their applications in cryptography and error checking of programs " the Turing Award.


Blum studied at MIT, earned his bachelor's degree in 1959 and his master's degree in electrical engineering in 1961 and received his Ph.D. in mathematics under Marvin Minsky in 1964. Subsequently he worked until 2000 as a professor of computer science at the University of California, Berkeley.

Currently, he is Bruce Nelson Professor of computer science at Carnegie Mellon University, where his wife, Lenore Blum, and his son, Avrim Blum teach, as computer science professors.


In the 1960s, he developed an independent concrete machine models axiomatic complexity theory based on a Gödel numbering and the Blum 's axioms. This theory provided concrete results as the compression theorem, the gap theorem of Borodin and the famous Blumsche speedup theorem.

His other works include a linear time selection algorithm, the Blum -Blum- Shub generator, the Blum - Goldwasser cryptosystem and more recently CAPTCHAs.

His graduate students have made with an unusual frequency of significant academic careers, including Leonard Adleman, Shafrira Goldwasser, Russell Impagliazzo, Silvio Micali, Gary L. Miller, Moni Naor, Steven Rudich, Michael Sipser, and Umesh and Vijay Vazirani.

Awards (selection)