David S. Johnson

180 Park Ave - Building 103

Florham Park, NJ

David S. Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his Ph.D from MIT.

The author of over 100 technical papers, he is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize of the Operations Research Society of America (1979). His research interests (in addition to the theory of NP-completeness) include approximation algorithms for combinatorial problems, and the experimental analysis of algorithms, with special emphasis on bin packing, graph coloring, and the traveling salesman problem. As one of the founders of ACM's Kanellakis Prize, he is particularly interested in recognizing and encouraging the interaction between theory and practice in computer science.

Technical Documents

Resource-Based Corruptions and the Combinatorics of Hidden Diversity

David Johnson, Juan Garay, Aggelos Kiayias, Moti Yung

ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp 4,
2013.
[PDF]
[BIB]

ACM Copyright

A brief history of NP-completeness, 1954-2012

David Johnson

Documenta Mathematica, Extra Volume: "Optimization Stories" Marrtin Grotschel, Editor, pp ,
2012.
[PDF]
[BIB]

DOCUMENTA MATHEMATICA Copyright

Network architecture for joint failure recovery and traffic engineering

Dahai Xu, Robert Doverspike, David Johnson, Martin Suchara, Jennifer Rexford

Sigmetrics 2011,
2011.
[PDF]
[BIB]

ACM Copyright

Voting power and target-based site prioritization

Steven Phillips, Aaron Archer, David Applegate, David Johnson, Robert Pressey, Desmond Torkornoo, Matthew Watts

Biological Conservation,
2010.
[PDF]
[BIB]

Elsevier Copyright

Awards

Knuth Prize 2009. David S. Johnson Named 2009 Knuth Prize Winner for Innovations that Impacted the Foundations of Computer Science

SIAM Fellow, 2009. For contributions to algorithms and complexity theory.

INFORMS Computing Society Prize, 2007.

AT&T Fellow, 2005. Application of Algorithms: Honored for fundamental contributions to the field of computer science and the application of algorithms to problems of importance to AT&T.

ACM Fellow, 1995. For fundamental contributions to the theories of approximation algorithms and computational complexity, and for outstanding service to ACM.

Knuth Prize 2009. David S. Johnson Named 2009 Knuth Prize Winner for Innovations that Impacted the Foundations of Computer Science

SIAM Fellow, 2009. For contributions to algorithms and complexity theory.

INFORMS Computing Society Prize, 2007.

AT&T Fellow, 2005. Application of Algorithms: Honored for fundamental contributions to the field of computer science and the application of algorithms to problems of importance to AT&T.

ACM Fellow, 1995. For fundamental contributions to the theories of approximation algorithms and computational complexity, and for outstanding service to ACM.

Connections