BY CHRISTOS H. PAPADIMITRIOU

DAVID STIFLER JOHNSON, the gentle pioneer, curator, and master expositor of hard computational problems and for decades the spirit, voice, and memory of the field of theoretical computer science, died March 8, 2016, aged 70.

He was born in Washington, DC, on December 9, 1945. Raised and schooled in Wisconsin, he kept it in his heart throughout his life, returning often, once to teach for a year at the University of Wisconsin–Madison (1980–81). In the late 1970s he was reunited in New Jersey with his lab mate from high school, Dorothy E. Wilson, and the two were married until his death.

David graduated summa cum laude from Amherst College in 1967 in mathematics and went on to obtain an MS from the Massachusetts Institute of Technology in 1968, also in math. Then he was drafted to the US Army at the height of the Vietnam War, but served as a 1st lieutenant in South Korea. An apocryphal explanation of this rather surprising deployment is that, during basic training, David humored his boredom by reading dusty Army rule books, where he learned that (1) a soldier’s volunteering for hardship cannot be declined, and (2) serving in Korea was still considered a hardship (even though the Korean War had been over for 16 years). The rules were quickly updated, but David got to spend his full service time in South Korea.

He returned from northeast Asia to MIT for his math PhD in 1971. His advisor was Michael J. Fischer, but it was Albert R. Meyer who suggested to him the study of approximation algorithms for hard optimization problems. That was a watershed moment.

Computers were solving more and more sophisticated problems, and yet over the previous two decades evidence had been accumulating that certain other practically important problems seemed to resist efficient solution. The theory of computation—focusing at the time on decidability and automata—appeared unable to provide an explanation, and this frustration had started to be articulated in, for example, the work of Jack Edmonds in the mid-1960s.

During the first year of David’s doctoral studies, an explanation was discovered: Stephen A. Cook and Richard M. Karp demonstrated that the resistant problems were NP-complete— assuming that P ≠ NP (a profound conjecture that is still unproved but widely accepted), they cannot be solved in polynomial time. This discovery marked the beginning of the modern era of the theory of computation—the theory of algorithms and complexity.

David Johnson’s contributions to this important intellectual edifice, which has transformed the practice of all of computer science, were crucial and twofold: he was the prime exegete of the theory of computationt through his book and expository writings, and he was the first to articulate one of its most productive branches: In his 1973 PhD thesis and in a complementary 1973 paper, he laid the foundations of the study of approximation algorithms. Since exact solutions to NP-complete optimization problems—such as the traveling salesman problem—seem to be beyond reach, one seeks efficient algorithms that produce solutions guaranteed to be near optimal. More than 4 decades later, this remains one of the most active research fronts in the field of algorithms and complexity. David contributed crucially to its early development.

Upon graduation from MIT, he became a technical staff member at Bell Labs (changed to AT&T Labs in 1996), where he remained until 2014, when he joined Columbia University as a visiting professor.

During many of his years at the labs he was manager of the theory group. He collaborated frequently with fellow researcher Michael R. Garey, and in 1979 the two published Computers and Intractability: A Guide to the Theory of NP‐ Completeness (W.H. Freeman), a book that would become legend. A masterful introduction to this difficult subject for the motivated inexpert reader, it goes far beyond that. With 57,000 citations—possibly the most-referenced work in all of computer science—it set the style and notation for the whole area and became an indispensable research tool through its annotated catalogue of NP-complete problems. Furthermore, from 1982 to 1992 David wrote a regular column in the Journal of Algorithms exploring new dimensions of intractability, a kind of continuous revision and updating of the book.

Theory aside, David was deeply interested in how difficult each of these problems really is in practice, and he was frustrated that such information was very difficult to fathom in the literature. From 1990 onward, he labored on the experimental analysis of algorithms for hard problems and sought to turn this craft into a domain of applied science by setting its principles and standards and enriching it with powerful examples. He also organized, at the Rutgers-based Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) that he helped found, a series of implementation challenges, biennial contests each focusing on a practically important computational problem.

David Johnson was a dedicated, valuable, and creative servant of his scientific community who never missed an annual meeting in his fields of interest. He transformed the Association for Computing Machinery (ACM)’s Special Interest Group on Algorithms and Computation Theory (SIGACT), the main professional society of theoretical computer scientists, both as its yeoman leader (1987–91) and as its face and voice during the following decades. He founded the annual Symposium on Discrete Algorithms (SODA) of the Society of Industrial and Applied Mathematics. And in the decades before Google Scholar, he published meticulous and valued bibliographies.

His contributions and achievements were rocognized with various honors. In 1995 he became an ACM fellow; in 1997 he received the inaugural SIGACT Distinguished Service Prize; in 2010 he was selected for the Knuth Prize, the prestigious career award for theoreticians; and he was elected to the National Academy of Engineering weeks before his death. Nobody in our research community will forget David Johnson, his friendly and mild manner, his partiality to CocaCola and plain food, his loyalty to the field, his humor, and his smile—easy, deep, bright, and yet not devoid of a subtle tone of melancholy. A science fiction collector and aficionado, he was also a long-distance runner who, tragically, lost a leg to amputation months before his untimely death. He is survived by Dorothy and their son Jack.