Manuel Blum
Encyclopedia
Manuel Blum 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".
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. In 2002 he was elected to the United States National Academy of Sciences
.
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.
. 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
s.
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
, Ronitt Rubinfeld, Luis von Ahn
, and Ryan Williams
.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
who received the Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
in 1995 "In recognition of his contributions to the foundations of computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and its application to cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and program checking".
Biography
Blum attended MIT, where he received his bachelor's degreeBachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
and his master's degree
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
in EECS in 1959 and 1961 respectively, and his Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
in 1964 under professor Marvin Minsky
Marvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
.
He worked as a professor of computer science at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
until 1999. In 2002 he was elected to the United States National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
.
He is currently the Bruce Nelson Professor of Computer Science at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
, where his wife, Lenore Blum
Lenore Blum
Lenore Blum is a distinguished professor of Computer Science at Carnegie Mellon. She received her Ph.D. in mathematics from the Massachusetts Institute of Technology in 1968. Her dissertation was on Generalized Algebraic Structures and her advisor was Gerald Sacks...
, and son, Avrim Blum
Avrim Blum
Avrim Blum is a prominent computer scientist who in 2007 was inducted as a Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms."-Biography:...
, 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 axiomsBlum axioms
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967....
. Even though the theory is not based on any machine model it yields concrete results like the compression theorem
Compression theorem
In computational complexity theory the compression theorem is an important theorem about the complexity of computable functions.The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions.-Compression theorem:Given a Gödel...
, the gap theorem
Gap theorem
In computational complexity theory the Gap Theorem is a major theorem about the complexity of computable functions.It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes...
, 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
Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list . This includes the cases of finding the minimum, maximum, and median elements. There are O, worst-case linear time, selection algorithms...
, the Blum Blum Shub pseudorandom number generator, the Blum-Goldwasser cryptosystem
Blum-Goldwasser cryptosystem
The Blum-Goldwasser cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum-Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion...
, and more recently CAPTCHA
CAPTCHA
A CAPTCHA is a type of challenge-response test used in computing as an attempt to ensure that the response is generated by a person. The process usually involves one computer asking a user to complete a simple test which the computer is able to generate and grade...
s.
His PhD Advisees, with unusual frequency, have gone on to very distinguished careers. Among them are Leonard Adleman
Leonard Adleman
Leonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...
, Shafi Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, Russell Impagliazzo
Russell Impagliazzo
Russell Impagliazzo is a professor of computer science at the University of California, San Diego. He received his doctorate from the University of California, Berkeley. His advisor was Manuel Blum. He spent two years as a postdoc at the University of Toronto. He is a 2004 Guggenheim fellow...
, Silvio Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
, Gary Miller
Gary Miller (professor)
Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 2003, he won the ACM Paris Kanellakis Award for the Miller–Rabin primality test. He was also made an ACM Fellow in 2002....
, Moni Naor
Moni Naor
Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His adviser was Manuel Blum....
, Steven Rudich
Steven Rudich
Steven Rudich is a professor in the Carnegie Mellon School of Computer Science. In 1994, he and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs were unlikely to answer many of the important problems in computational complexity theory. For this work,...
, Michael Sipser
Michael Sipser
Michael Fredric Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. He received his Ph.D. in 1980 from the University of California, Berkeley under the direction of Manuel Blum....
, Umesh
Umesh Vazirani
Umesh Virkumar Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
and Vijay Vazirani
Vijay Vazirani
Vijay Virkumar Vazirani is an Indian American Professor of Computer Science at Georgia Tech.He received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian...
, Ronitt Rubinfeld, Luis von Ahn
Luis von Ahn
Luis von Ahn is an entrepreneur and an associate professor in the Computer Science Department at Carnegie Mellon University. He is known as one of the pioneers of the idea of crowdsourcing. He is the founder of the company reCAPTCHA, which was sold to Google in 2009...
, and Ryan Williams
Ryan Williams (computer scientist)
Richard Ryan Williams is an American computer scientist working in computational complexity theory.-Education:Williams received his Ph.D in computer science in 2007 from Carnegie Mellon University under the supervision of Manuel Blum. As of 2010, he is a member of the Theory Group of IBM Almaden...
.
See also
- Blum complexity axioms
- Blum's speedup theoremBlum's speedup theoremIn computational complexity theory Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions....
- Blum Blum Shub
- Blum-Goldwasser cryptosystemBlum-Goldwasser cryptosystemThe Blum-Goldwasser cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum-Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion...