tag:blogger.com,1999:blog-3722233.post4317983773889402361..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: David Johnson (1945-2016)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-3722233.post-60947648134338338192016-04-13T15:47:02.034-05:002016-04-13T15:47:02.034-05:00This is very sad news. The list of ways in which D...This 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.Matt Stallmannhttp://people.engr.ncsu.edu/mfmsnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32661767532552476922016-04-13T15:41:56.368-05:002016-04-13T15:41:56.368-05:00This is very sad news indeed. The list of ways in ...This 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.Matt Stallmannhttp://people.engr.ncsu.edu/mfmsnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64215360704530420602016-03-19T15:40:04.454-05:002016-03-19T15:40:04.454-05:00I was very sad to hear this news. David's work...I 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.samirhttps://www.blogger.com/profile/12398855828681012949noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37712709254404820052016-03-17T13:50:14.020-05:002016-03-17T13:50:14.020-05:00David was not only a great scientist but also a wo...David was not only a great scientist but also a wonderful person humble and modest in spite of his stature.,Ron PinterAnonymoushttps://www.blogger.com/profile/18111239931568085373noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54462206159266736912016-03-11T20:51:46.344-06:002016-03-11T20:51:46.344-06:00I enjoyed working with him in SIGACT leadership. I...I 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. <br /> -- Jeff Vitter (JSV@OleMiss.edu)Anonymoushttps://www.blogger.com/profile/04220172236204375118noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50503713934753572112016-03-10T02:58:46.582-06:002016-03-10T02:58:46.582-06:00I have known him since 1974 and had a discussions ...I 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. Cahithttps://neu-tr.academia.edu/IbrahimCahitnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41985423781259567482016-03-09T23:08:45.675-06:002016-03-09T23:08:45.675-06:00The classic pioneer book(1979) Computers and Intra...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. DGDebajyoti Ghoshhttps://www.blogger.com/profile/14979016987122846396noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8885449790591111802016-03-09T20:31:03.203-06:002016-03-09T20:31:03.203-06:00I was also lucky to be David's intern many yea...I was also lucky to be David's intern many years ago. He remained a mentor and friend ever since. <br /><br />Another 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.Cliff Steinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39213757059146919062016-03-09T20:20:04.961-06:002016-03-09T20:20:04.961-06:00Its hard to convey to people today how important t...Its hard to convey to people today how important the book (on paper)<br />Garey 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.<br /><br />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.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19164560000866537612016-03-09T19:55:19.959-06:002016-03-09T19:55:19.959-06:00David was very active in helping DIMACS succeed in...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.Eric Allenderhttps://www.blogger.com/profile/07417405562053586552noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67650349416582336912016-03-09T19:52:10.380-06:002016-03-09T19:52:10.380-06:00Terribly sorry to hear about this, my condolences ...Terribly sorry to hear about this, my condolences to Dorothy. <br /><br />Here 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. <br /><br />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.<br />Grigory Yaroslavtsevhttps://www.blogger.com/profile/13047893775057278591noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49453093358576860142016-03-09T18:39:48.944-06:002016-03-09T18:39:48.944-06:00A great guy and a great runner as well. I would l...A great guy and a great runner as well. I would like to think that he now knows the answer!Tom Szymanskinoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41350092732234486422016-03-09T14:50:07.073-06:002016-03-09T14:50:07.073-06:00David's intellect, dedication, and energy are ...David's intellect, dedication, and energy are an enduring<br />inspiration. He was my mentor on STOC and SIGACT<br />matters.<br />I always sought his advice, which was eagerly offered and always<br />the best. At TALG he was the best of editors, and I learned<br />a great deal from the little help I could give to make the columns<br />perfect. I miss his companionship and the warm hospitality he and<br />Dorothy shared. My deepest sympathies to Dorothy and the family.<br />Hal Gabowhttp://cs.colorado.edunoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82607848711520561832016-03-09T12:35:22.600-06:002016-03-09T12:35:22.600-06:00Is there a service?Is there a service?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15995299457802728842016-03-09T11:11:55.949-06:002016-03-09T11:11:55.949-06:00I think all of us who interned at AT&T Labs as...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 <i>David Johnson</i>! 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.AChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56995188099151211432016-03-09T10:27:58.630-06:002016-03-09T10:27:58.630-06:00Condolences to David's family. I loved the BB...Condolences 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.<br /><br />Albert Greenberg Albert Greenbergnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35077781770639158412016-03-09T10:13:30.081-06:002016-03-09T10:13:30.081-06:00I feel very sad about this. I respected him and hi...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.Kamal Jainhttps://www.blogger.com/profile/11174764456072833559noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24445636363178210752016-03-09T09:30:23.331-06:002016-03-09T09:30:23.331-06:00This is a shock - I thought he was recovering. Lik...This 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. <br /><br />My best wishes to his family.Aravindhttp://www.cs.umd.edu/~srinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30333550838024795432016-03-09T09:06:30.099-06:002016-03-09T09:06:30.099-06:00I still cannot believe this. I was fortunate to in...I 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.Barnahttp://barnasaha.netnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89672509459699063222016-03-09T08:11:27.014-06:002016-03-09T08:11:27.014-06:00Very sad. I knew that he was unwell. He was still ...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.Chandrahttps://www.blogger.com/profile/00057069075567569157noreply@blogger.com