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 ...

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.

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