

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.