### Manuel Blum

Born 26 April 1938, Caracas, Venezuela

Turing Award (1995) “in recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking”

Manuel Blum’s parents fled crisis-torn Europe for South America (Venezuela) where their son was born (1938). As a child, Blum expressed great interest in how the brain works because, as he later said in an interview, “I was a dumb kid and wanted to be smarter”. He enrolled in 1955 at MIT as a student of Electrical Engineering “in the hope of building electronic brains” and worked in the Neurophysiology Laboratory of Dr. Warren S. McCulloch. In the following years, he pursued his interest in mathematical problems of neuroscience and, under the supervision of the pioneer of Artificial Intelligence Marvin Minsky (also a Turing Award winner), he received his Ph.D. in Mathematics in 1964. His doctoral thesis, “A Machine-Independent Theory of the Complexity of Recursive Functions” contains the surprising “speed-up” theorem. Blum began his academic career as an assistant professor at MIT. In 1968 he moved to the University of California at Berkeley, where from 1977 to 1980 he was Associate Chair of Computer Science (CS) and from 1995 held the Arthur J. Chick Chair in CS. After a sabbatical as Visiting Professor in Hong Kong from 1997 to 1999, Blum and his wife Lenore joined their son Avrim as professors of CS at Carnegie Mellon University in Pittsburgh, where Manuel holds the Bruce Nelson Chair of CS.

Manuel Blum is a member of the National Academies of Sciences and Engineering, the American Academy of Arts and Sciences and the American Association for the Advancement of Science. He is the recipient of several awards for outstanding teaching including Sigma Xi’s Monie A. Ferst Award (1991). His Ph.D. students are amongst the most renowned in CS and include three Turing Award winners.

How difficult is it to find the median of a set of numbers? Or to decide whether or not it is possible to divide a set of numbers into two subsets such that the sums of their elements are the same? The difficulty of such problems is studied in Complexity Theory, and this is Manuel Blum’s field. The core problem of complexity theory is this: If you know an algorithm that solves a problem with a certain speed, this does not imply that there are no faster algorithms. Only for a few problems is it actually known how quickly they can be (theoretically) solved. The median problem above is an example: along with Vaughan Pratt and Turing Award winners, Bob Floyd, Ron Rivest and Bob Tarjan, Blum showed this can be solved in linear time which is optimal.

Another area is the exploration of chance. One result, together with Lenore Blum and Michael Shub, is the Blum-Blum-Shub generator for pseudo-random numbers. With the BBS generator, a computer can generate number sequences that are indistinguishable (in a complexity theoretic sense) from random numbers.

Blum is also known for surprising solutions to problems in cryptography, which has led to the fields of zero knowledge and interactive proofs, developed by his students, Shafi Goldwasser and Silvio Micali, also Turing Award winners. Suppose two people – usually called Alice and Bob – toss a coin. ‘They have just divorced, live in different cities, want to decide who gets the car’, begins Blum’s work “Coin flipping by telephone – A protocol for solving impossible problems” (1981), in which he gives a protocol that solves the problem. The idea can be easily explained. Alice throws the coin and packs the result into a mathematical function. She sends the result to Bob, who guesses out loud what Alice may have thrown. Then he receives from her a mathematical key, to see if his guess was correct. Afterwards both know whether Bob’s guess was correct or not – and in any case, the result is wholly dependent on chance. Another application of the idea was presented in his 1986 International Congress of Mathematicians talk, “How to prove a theorem so no one else can claim it”.

In his spare time Manuel Blum writes poems, including Japanese haiku.