David's 1979 book with Michael Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness, is still the best reference on the topic and perhaps the single most important resource in any computer scientist's library. David Johnson also 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. David founded the Symposium on Discrete Algorithms (SODA), a conference that is now often mentioned with STOC and FOCS as a top theory venue. He created the DIMACS algorithms challenges. He led SIGACT from 1987-1991, really transforming that organization, and served as its face for many years thereafter. I'm only scratching the surface of what he's done for the community, and can think of no one who put more effort into making the theoretical computer science as strong as it is.
Of course David was a great researchers as well, working on NP-completeness and approximation algorithms.
He received an ACM Fellow in 1995, 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 our algorithms. Just last month he was elected into the National Academy of Engineering.
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.
Very sad. I knew that he was unwell. He was still hoping to attend the next STOC when I wrote to him a few months back. I fondly remember the annual barbecue at his house during my Bell Labs years. RIP David.
ReplyDeleteI still cannot believe this. I was fortunate to interact with David closely at AT&T labs. I knew about his struggle against cancer, but was hoping so much he would win the battle. You will be dearly missed David. RIP.
ReplyDeleteThis is a shock - I thought he was recovering. Like for Chandra, the annual barbecue that Dorothy and David hosted in NJ is a fond memory for me.
ReplyDeleteMy best wishes to his family.
I feel very sad about this. I respected him and his work. When I graduated, I had an offer from him to join his group, which I regretfully declined and missed an opportunity to work with him. When I was at eBay, I approached him to lead eBay research labs. I was not aware of his personal challenges but he still gave a lot of thought to the proposal. David, your service to the computer science community is second to none, and you will always be remembered for the work, including the famous Garey-Johnson book, you have accomplished.
ReplyDeleteCondolences to David's family. I loved the BBQs, and getting to know David. His take on hard problems, such as the traveling salesman problem, was inspiring, practical and impactful.
ReplyDeleteAlbert Greenberg
I think all of us who interned at AT&T Labs as grad students fondly recall David and his barbecue tradition. In my case I can also recall the feeling that I was sitting 20 metres away from David Johnson! and how that feeling grew from mere fandom to a more mature deep respect as I got to know David better through that summer. I knew a little of David's struggles with health during these last several months, but this news is still very sad to hear. RIP, David.
ReplyDeleteIs there a service?
ReplyDeleteDavid's intellect, dedication, and energy are an enduring
ReplyDeleteinspiration. He was my mentor on STOC and SIGACT
matters.
I always sought his advice, which was eagerly offered and always
the best. At TALG he was the best of editors, and I learned
a great deal from the little help I could give to make the columns
perfect. I miss his companionship and the warm hospitality he and
Dorothy shared. My deepest sympathies to Dorothy and the family.
A great guy and a great runner as well. I would like to think that he now knows the answer!
ReplyDeleteTerribly sorry to hear about this, my condolences to Dorothy.
ReplyDeleteHere is some random sample of memories. I first met David when he came to St. Petersburg to teach a class on bin packing as a part of a summer school organized by Microsoft Research. This school was terrific and was one of those things that inspired me to apply to do grad school in the U.S. Next time I ran into David was during a poster session at STOC -- he stopped by to ask me about my poster on approximation algorithms for spanners. Explaining the paper to David made the entire hassle of making the poster worthwhile. Just as Amit later I was lucky to intern at AT&T when David was still the head of the algorithms group there and I enjoyed that time a lot. Every day David would gather us together for lunch at the theory table with all other great members that the group had at the time.
I also remember asking David what he would consider his main contribution to computer science. His answer was that back in 1973 he wrote a paper "Approximation algorithms for combinatorial problems" which essentially introduced this new field.
David was very active in helping DIMACS succeed in its many endeavors. He always had lots of insightful advice and good suggestions. He was an inspiring researcher, and a tremendous asset to the entire research community. He will be greatly missed.
ReplyDeleteIts hard to convey to people today how important the book (on paper)
ReplyDeleteGarey and Johnson was. There were some papers in some conference proceedings on P/NP but no central place. This was pre-web! To gather it all up, sythesize it, and get a book out that told you what you needed to know to get started in research, and was well written, was really needed.
For several years he wrote a column on P vs NP to update the book. The columns are worth reading and available for free at his website.
I was also lucky to be David's intern many years ago. He remained a mentor and friend ever since.
ReplyDeleteAnother pre-web memory was that David published the STOC/FOCS bibliography sometime around 1990. He tracked down (almost) every STOC/FOCS paper ever published, and reported on where the journal version appeared. There were also comments about known errors or major followup work. It was very useful to have.
The classic pioneer book(1979) Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson will remain a good reference forever. DG
ReplyDeleteI have known him since 1974 and had a discussions on max-clique problem and learned from him a lot on his favorite topic bin-packing.RIP, David Johnson.
ReplyDeleteI enjoyed working with him in SIGACT leadership. I was fortunate to first learn about David thru the preprint of his book with Mike Garey that we used in Bob Tarjan's complexity class when I was a grad student at Stanford in the late 1970s. David was very instrumental in starting SODA and championing the importance of algorithms. He will be greatly missed.
ReplyDelete-- Jeff Vitter (JSV@OleMiss.edu)
David was not only a great scientist but also a wonderful person humble and modest in spite of his stature.,Ron Pinter
ReplyDeleteI was very sad to hear this news. David's work of course has made a huge impression on many many researchers in the field, and its impact felt by all of us who have used the great Garey and Johnson book for the last 30+ years. David was instrumental in launching the SODA conferences, among his many other contributions to our field. Rest in peace David.
ReplyDeleteThis is very sad news indeed. The list of ways in which David has had an impact on my career and on computer science as a whole is long. I will continue to value his mentorship in the world of experimental algorithms, where he was one of the pioneers. My thoughts and prayers are with his family and all those closest to him. I will miss David.
ReplyDeleteThis is very sad news. The list of ways in which David has had an impact on the field of computer science and on my own career is long. I especially value his mentorship in the world of experimental algorithms, where he was a pioneer. My thoughts and prayers are with his family and friends. I will miss David.
ReplyDelete