Manuel Blum (born 26 April 1938) is a Venezuelan-American
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
who received the Turing Award in 1995 "In recognition of his contributions to the foundations of
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
and its application to
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
and program checking".
Education
Blum was born to a
Jewish
Jews ( he, יְהוּדִים, , ) or Jewish people are an ethnoreligious group and nation originating from the Israelites Israelite origins and kingdom: "The first act in the long drama of Jewish history is the age of the Israelites""The ...
family in Venezuela. Blum was educated at
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
, where he received his bachelor's degree and his master's degree in
electrical engineering
Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems which use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...
in 1959 and 1961 respectively, and his
Ph.D.
A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...
in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
in 1964 supervised by
Marvin Minsky
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, an ...
.
[.]
Career
Blum worked as a professor of computer science at the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...
until 2001. From 2001 to 2018, he was the Bruce Nelson Professor of Computer Science at
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
, where his wife,
Lenore Blum
Lenore Carol Blum (née Epstein, born December 18, 1942) is an American computer scientist and mathematician who has made pioneering contributions to the theories of real number computation, cryptography, and pseudorandom number generation. She ...
, was also a professor of Computer Science.
In 2002, he was elected to the
United States National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nati ...
. In 2006, he was elected a member of the
National Academy of Engineering
The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...
for contributions to abstract complexity theory, inductive inference, cryptographic protocols, and the theory and applications of program checkers.
In 2018 he and his wife Lenore resigned from Carnegie Mellon University to protest against sexism after a change in management structure of
Project Olympus led to sexist treatment of her as director and the exclusion of other women from project activities.
Research
In the 60s he developed an axiomatic complexity theory which was independent of concrete machine models. The theory is based on
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...
s and the
Blum axioms In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967.
Importantly ...
. Even though the theory is not based on any machine model it yields concrete results like the
compression theorem In computational complexity theory, the compression theorem is an important theorem about the Computational complexity, complexity of computable functions.
The theorem states that there exists no largest complexity class, with computable boundary, ...
, the
gap theorem
:''See also Gap theorem (disambiguation) for other gap theorems in mathematics.''
In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable fun ...
, the honesty theorem and the
Blum speedup theorem.
Some of his other work includes a protocol for
flipping a coin over a telephone,
median of medians
In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the ''k''th smallest element of an initially u ...
(a linear time
selection algorithm
In computer science, a selection algorithm is an algorithm for finding the ''k''th smallest number in a list or array; such a number is called the ''k''th ''order statistic''. This includes the cases of finding the minimum, maximum, and median e ...
), the
Blum Blum Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form
:x_ = x_n^2 \bmod M,
where ...
pseudorandom number generator, the
Blum–Goldwasser cryptosystem
The Blum–Goldwasser (BG) 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 expans ...
, and more recently
CAPTCHA
A CAPTCHA ( , a contrived acronym for "Completely Automated Public Turing test to tell Computers and Humans Apart") is a type of challenge–response test used in computing to determine whether the user is human.
The term was coined in 2003 ...
s.
[Von Ahn, Luis; Blum, Manuel; Hopper, Nicholas J.; Langford, John (May 2003).]
CAPTCHA: Using Hard AI Problems for Security
. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2003).
Blum is also known as the advisor of many prominent researchers. Among his Ph.D. students are
Leonard Adleman
Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...
,
Dana Angluin
Dana Angluin is a professor emeritus of computer science at Yale University. She is known for foundational work in computational learning theory and distributed computing.
Education
Angluin received her B.A. (1969) and Ph.D. (1976) at University ...
,
Shafi Goldwasser
en, Shafrira Goldwasser
, name = Shafi Goldwasser
, image = Shafi Goldwasser.JPG
, caption = Shafi Goldwasser in 2010
, birth_place = New York City, New York, U.S.
, birth_date =
, death_date ...
,
Mor Harchol-Balter,
Russell Impagliazzo,
Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security.
In 2012, he received ...
,
Gary Miller Gary Miller may refer to:
*Gary Miller (politician) (born 1948), American politician
* Michael Dunn (actor) (Gary Neil Miller, 1934–1973), American actor
* Gary L. Miller (1947–1969), American soldier and Medal of Honor recipient
* Gary Miller ...
,
Moni Naor
Moni Naor ( he, מוני נאור) 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 advisor was Manuel Blum.
He works i ...
,
Steven Rudich
Steven Rudich (born October 4, 1961) 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, was unlikely to answer many of ...
,
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massa ...
,
Ronitt Rubinfeld
Ronitt Rubinfeld is a professor of electrical engineering and computer science at MIT.
Education
Rubinfeld graduated from the University of Michigan with a BSE in Electrical and Computer Engineering. Following that, she received her PhD from th ...
,
Umesh Vazirani
Umesh Virkumar Vazirani is an Indian-American academic who 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. Hi ...
,
Vijay Vazirani
Vijay Virkumar Vazirani ( hi, विजय वीरकुमार वज़ीरानी; b. 1957) is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the Universi ...
,
Luis von Ahn
Luis von Ahn (; born 19 August 1978) is a German-Guatemalan entrepreneur and a consulting professor in the Computer Science Department at Carnegie Mellon University in Pittsburgh, Pennsylvania. He is known as one of the pioneers of crowdsourcin ...
, and
Ryan Williams.
See also
*
List of Venezuelans
Famous or notable Venezuelans include:
Architecture
* Jimmy Alcock
* Esther Ayuso
* Federico Beckhoff
*Anita Berrizbeitia
* Guido Bermudez
* Bernardo Borges
* Dirk Bornhost
*Carlos Brillembourg
* Cipriano Dominguez
* Julián Ferris Betanc ...
*
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational compl ...
*
Non-interactive zero-knowledge proof
Non-interactive zero-knowledge proofs are zero-knowledge proofs where information between a prover and a verifier can be authenticated by the prover, without revealing any of the specific information beyond the validity of the transaction itself. T ...
*
Quantum coin flipping
*
Pancake sorting
References
{{DEFAULTSORT:Blum, Manuel
American computer scientists
Theoretical computer scientists
1938 births
Living people
Jewish American scientists
International Association for Cryptologic Research fellows
Members of the United States National Academy of Engineering
Members of the United States National Academy of Sciences
Turing Award laureates
Carnegie Mellon University faculty
UC Berkeley College of Engineering faculty
Venezuelan emigrants to the United States
Venezuelan Jews
Massachusetts Institute of Technology School of Science alumni
20th-century American engineers
21st-century American engineers
20th-century American scientists
21st-century American scientists
MIT School of Engineering alumni