In Memoriam: David S. Johnson

CRA regrets to report that former CRA board member David S. Johnson, 70, passed away on March 8. He was a leader and advocate for algorithms and all of theoretical computer science.

David wrote the NP-completeness column for the Journal on Algorithms and later the ACM Transactions on Algorithms, as well as “A Catalog of Complexity Classes” for the 1990 Handbook of Theoretical Computer Science. He founded the Symposium on Discrete Algorithms (SODA), a conference that is now often mentioned with STOC and FOCS as a top theory venue. He also created the DIMACS algorithms challenges, and led SIGACT from 1987-1991, during which time he transformed the organization. David also served as its face for many years thereafter.

David became an ACM Fellow in 1995, and received the first SIGACT Distinguished Service prize in 1997 and the Knuth Prize in 2010. He used his Knuth Prize lecture to push for practical applications for algorithms. Last month, he was elected into the National Academy of Engineering.

Former CRA board member Lance Fortnow recently wrote about David on his blog Computational Complexity:

“I worked with David Johnson closely on various SIGACT activities. David never missed a STOC and we always invited him to the SIGACT Executive Committee dinners, not because he had an official role, but because he was David Johnson. I truly respected and admired David and glad I could call him a friend. We’ll miss him deeply. STOC and SODA just won’t be the same without him.”