# David S. Johnson

> American computer scientist (1945-2016)

**Wikidata**: [Q92801](https://www.wikidata.org/wiki/Q92801)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/David_S._Johnson)  
**Source**: https://4ort.xyz/entity/david-s-johnson

## Summary
David S. Johnson was an American computer scientist and university teacher known for fundamental contributions to algorithms, complexity theory, and mathematical optimization. He was a long-time faculty member at Columbia University and a recipient of major honors including the Knuth Prize (2010) and the Frederick W. Lanchester Prize (1979).

## Biography
- Born: 1945-12-09, Washington, D.C.
- Nationality: United States
- Education: Amherst College; Massachusetts Institute of Technology
- Known for: Contributions to algorithms, complexity theory, informatics, and mathematical optimization
- Employer(s): Columbia University
- Field(s): Computer science; informatics; algorithms; mathematical optimization

## Contributions
David S. Johnson produced an extensive body of scholarly work in algorithms and optimization. He is documented in major bibliographic and author databases (dblp author id j/DavidSJohnson, MathSciNet author id 193251, Open Library author OL1338075A, Google Scholar author id LyEq7qEAAAAJ), indicating a sustained publication record in theoretical computer science and applied optimization. His research earned him major prizes: the Frederick W. Lanchester Prize in 1979 and the Knuth Prize in 2010, and professional recognition as an ACM Fellow (1995) and a SIAM Fellow (2009) for contributions to algorithms and complexity theory. He completed doctoral work under Michael J. Fischer and held an academic appointment at Columbia University. His connectivity in the research community is reflected by an Erdős number of 2. Johnson’s work is cataloged across library and authority files (ISNI 000000011452337X, VIAF 94766987, Library of Congress n78052545), showing broad dissemination and citation of his publications across the fields of computer science and informatics.

## FAQs
### Q: Who was David S. Johnson?
A: David S. Johnson was an American computer scientist and university teacher noted for contributions to algorithms, complexity theory, and mathematical optimization. He served on the faculty of Columbia University.

### Q: When did David S. Johnson live?
A: He was born on December 9, 1945, in Washington, D.C., and died on March 8, 2016.

### Q: What major awards did he receive?
A: He received the Frederick W. Lanchester Prize (1979) and the Knuth Prize (2010), and he was named an ACM Fellow (1995) and a SIAM Fellow (2009).

## Why They Matter
David S. Johnson’s career combined foundational research, teaching, and broad scholarly dissemination in algorithms and optimization. His work was recognized by leading professional societies (ACM, SIAM) and by prestigious awards that mark lasting impact on theoretical computer science. The Frederick W. Lanchester Prize and the Knuth Prize attest to both specific published contributions and a sustained record of influential research. His doctoral training under Michael J. Fischer and his Erdős number of 2 reflect close collaboration within the theoretical community. Johnson’s publications are indexed across major bibliographic services (dblp, MathSciNet, Open Library, Google Scholar), which signals extensive citation and use by other researchers. As a university teacher at Columbia University, he helped transmit methods in algorithms and optimization to students and peers. Without his contributions, the literature and collective understanding in algorithms and mathematical optimization would be missing recognized results and expository work that others have built on; his awards and fellowships indicate that many subsequent researchers and the computational mathematics community were influenced by his research and professional leadership.

## Notable For
- Recipient of the Knuth Prize (2010).
- Recipient of the Frederick W. Lanchester Prize (1979).
- Named an ACM Fellow (1995) for contributions to computing.
- Named a Fellow of the Society for Industrial and Applied Mathematics (2009) for contributions to algorithms and complexity theory.
- Longtime faculty member at Columbia University; doctoral advisor: Michael J. Fischer.  
- Erdős number: 2.

## Body

### Personal and identity
- Full name: David Stifler Johnson (also credited as David Johnson, David S. Johnson).
- Born: 1945-12-09 in Washington, D.C.
- Died: 2016-03-08.
- Sex/gender: male.
- Citizenship: United States.
- Languages: English.

### Education and academic lineage
- Undergraduate and/or early education: Amherst College (listed as educated_at).
- Graduate education: Massachusetts Institute of Technology (listed as educated_at).
- Doctoral advisor: Michael J. Fischer.
- Mathematics Genealogy Project id: 77156.

### Employment and roles
- Employer: Columbia University (listed employer).
- Occupation: computer scientist, engineer, university teacher.
- Fields of work: computer science, informatics, algorithms, mathematical optimization.

### Awards and honors
- Frederick W. Lanchester Prize — 1979.
- ACM Fellow — 1995.
- SIAM Fellow (Fellow of the Society for Industrial and Applied Mathematics) — 2009; cited for contributions to algorithms and complexity theory.
- Knuth Prize — 2010.
- Member of the US National Academy of Engineering (member id 149872).

### Publications and scholarly presence
- Indexed author identifiers:
  - dblp author id: j/DavidSJohnson
  - MathSciNet author id: 193251
  - Open Library author id: OL1338075A
  - Google Scholar author id: LyEq7qEAAAAJ
  - zbMATH author id: johnson.david-stifler
- Authority and library identifiers:
  - ISNI: 000000011452337X
  - VIAF: 94766987
  - GND: 118004858X
  - Library of Congress: n78052545
  - National Library identifiers across multiple countries.

### Professional memberships
- Association for Computing Machinery — ACM Fellow (membership recorded from 1995).
- Society for Industrial and Applied Mathematics — SIAM Fellow (2009).

### Community indicators
- Erdős number: 2.
- Widely represented in Wikipedia and multiple language editions (wikipedia_title: David S. Johnson; languages listed).

## Schema Markup
```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "David S. Johnson",
  "jobTitle": "Computer scientist; university teacher",
  "worksFor": {
    "@type": "Organization",
    "name": "Columbia University"
  },
  "nationality": {
    "@type": "Country",
    "name": "United States"
  },
  "birthDate": "1945-12-09",
  "birthPlace": "Washington, D.C., United States",
  "alumniOf": [
    {
      "@type": "EducationalOrganization",
      "name": "Amherst College"
    },
    {
      "@type": "EducationalOrganization",
      "name": "Massachusetts Institute of Technology"
    }
  ],
  "knowsAbout": [
    "Computer science",
    "Algorithms",
    "Informatics",
    "Mathematical optimization"
  ],
  "sameAs": [
    "https://en.wikipedia.org/wiki/David_S._Johnson",
    "https://openlibrary.org/authors/OL1338075A/David_S._Johnson"
  ],
  "description": "American computer scientist known for contributions to algorithms, complexity theory, and mathematical optimization; recipient of the Knuth Prize (2010)."
}

## References

1. Virtual International Authority File
2. Czech National Authority Database
3. [Source](https://awards.acm.org/fellows/award-recipients)
4. [Source](https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows?page=2)
5. Mathematics Genealogy Project
6. International Standard Name Identifier
7. CiNii Research
8. [Source](https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows)
9. [Source](http://www.cs.columbia.edu/2016/david-johnson-in-memoriam/)
10. Freebase Data Dumps. 2013
11. [David S. Johnson | Open Library](https://openlibrary.org/authors/OL1338075A/David_S._Johnson)
12. IdRef
13. LIBRIS. 2018