David Stifler Johnson is a computer scientist

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

 specializing in algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s and optimization. He is currently the head of the Algorithms and Optimization Department of AT&T Labs

AT&T Labs

AT&T Labs, Inc. is the research & development division of AT&T, where scientists and engineers work to understand and advance innovative technologies relevant to networking, communications, and information. Over 1800 employees work in six locations: Florham Park, NJ; Middletown, NJ; Austin, TX;...

 Research. He was awarded the 2010 Knuth Prize

Knuth Prize

The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...

.

Johnson graduated summa cum laude from Amherst College

Amherst College

Amherst College is a private liberal arts college located in Amherst, Massachusetts, United States. Amherst is an exclusively undergraduate four-year institution and enrolled 1,744 students in the fall of 2009...

 in 1967, then earned his S.M. from MIT

Massachusetts Institute of Technology

The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

 in 1968 and his Ph.D. from MIT

Massachusetts Institute of Technology

The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

 in 1973. All three of his degrees are 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 1995 he was inducted as a Fellow

Fellow

A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...

 of the Association for Computing Machinery

Association for Computing Machinery

The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

. Johnson has Erdős number

Erdos number

The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...

 2.

He is the coauthor of Computers and Intractability: A Guide to the Theory of NP-Completeness (ISBN 0-7167-1045-5).

See also

• List of computer scientists
• List of important publications in computer science