MohammadTaghi HajiAghayi on David Johnson

More than a week ago, I heard the very sad news that David Johnson has passed away after one year fight with cancer. I felt that I should write a memorial note for him. Indeed I have done the same for Mihai Pătraşcu in the same blog and both Mihai and David were very similar to me from several aspects: both were my colleagues at AT&T and more importantly my dear friends, both they got their Ph.D. from MIT (the same place that I got my Ph.D. as well), they both were extraordinary researchers, and both passed away due to cancer after almost a year-long fight with it (and I was closely aware of their situations in that year). Indeed David read my memo for Mihai and he told me that he liked it. In addition, there is another reason that I feel respect for David; he was just a bit older than my father who also passed away very recently. So here I would like to put my thoughts into words for David (and this took me more time in this case since I wanted to mention some new thoughts given the comments already in this blog). To do so, I would like to mention some of David’s personal characteristics that I appreciated a lot and give some examples on them from my interactions with him. Indeed I have even mentioned some of these to him when he was alive and told him because of these (and other reasons), I am always proud to mention that I have him as my boss at some point in my career.

First of all, David was very humble and modest especially given his extraordinary CV: he won several awards especially Knuth prize, he is the co-author of one of the top most-cited books in CS, he was fellows of almost every community that he was involved with (e.g., ACM, SIAM, AT&T), he was a member and the chair of several prestigious award committees (like Gödel, Knuth, ACM Kanellakis, ACM Thesis Award) and indeed he was a founder of some of them (e.g., Kanellakis), and he was the founder of SODA, the best algorithms conference, among others. Despite all this he was a very humble and modest man and I think lots of people who interacted with him will fully agree on this. Just to give an example, in 1998, while I was still a second-year undergrad at Sharif University, I sent him an email asking whether he was aware of any book similar to Garey & Johnson but for parallel computing (indeed this was my first remote interaction with him); I was shocked how fast he answered my email just in a couple of hours with a relevant reference. This was especially very exciting and encouraging for me, since several other people never answered my emails at that time. More interestingly, later in 2012, I told him personally that I admired him for answering that email. He told me just wait a second and in a couple of minutes, he could find the exact same email from 1998 that I sent him; then we even discussed some English improvements for the email text as well.

Second he was a perfectionist from several aspects. Here are some examples. He was often the reviewer for P=NP or P!=NP papers for several journals. Probably lots of us even do not look into these papers unless written by a well-known fellow; however he was reading these papers very carefully to find the exact bugs and mention them to the authors. Indeed even when I sent him several referee requests for conferences for which I severed as a PC member, he always spent a lot of time to read the paper very carefully and often came with novel improvements and simplifications, sometime in a extend that authors of the paper under review wanted to have this anonymous referee as a co-author. All these happened despite he was a very busy man; however he still considered the task of refereeing a paper very seriously and respected the authors (and I think this is an example that lots of us can learn from it). He was a very good writer as well and spent a lot of time to improve the presentation of a paper, simplify it, and present it in a perfect way. I am proud to have one paper coauthored with David, a very long paper with several co-authors. On this paper David had the lead and indeed spent all the years that I was with AT&T (and even after than) to prepare the journal version of the paper. Indeed he was sending us the almost final version on Dec 2014 (and asked us for comments) just a month before he was diagnosed with cancer (I hope that still we can send the paper to a journal given the time that David spent on it). Another example of his perfectionism: he attended ALL SODA while he was alive and almost ALL STOC and FOCS (expect 1-2 years that AT&T had travel restrictions). Not only that, anytime that there was any talk in the conference, he attended at least one session. Yet another example: we had group lunches every day at AT&T.  That was David’s habit to ask everyone in the group to see whether they want to join. Now the interesting point was that he came exactly at noon EVERY DAY and you could even set your watch for 12pm when you saw him for lunch.

He was founder of SODA, the best algorithms conference. Indeed lots of us know David because he was the founder of SODA and he was handling SODA business meetings for lots of year as the chair of the steering committee. As a result, I often had lots of discussion with him regarding SODA and its future. We discussed what the protocol for selecting the chair of SODA should be, whether SODA should have an official Rebuttal Phase or not, etc. During discussion even some interesting topics came up which are good to discuss in the community as well. David believed since SODAs (and in general other major TCS conferences) are the main venues for publications but still we need full and correct mathematical proofs for our claims (despite the rest of CS), we should have a five-year period that any major claims and theorems for which the authors do not provide full proofs in a verifiable manner in arxiv or in a journal during these five years should be considered officially open for everyone to grab, prove formally, and get the full credit for that. Another discussion was that ideally SODA (and again other major TCS conferences) should go double-blind like lots of other major CS conferences in other fields. This will help to have much more fair selection in which the name of authors do not give advantage/disadvantage for acceptance (though PC chair still could see the author lists for some extreme cases).

I can probably write pages and pages of other memories on David’s excellent personal characteristics (e.g. he was a marathon runner, he held the annual barbecue for AT&T/Bell-labs theory interns, researchers, and alumni for more than two decades,  he served in Army between his Masters and Ph.D. and kept the same types of spirits and disciplines in the rest of his life, he always emphasized on putting his middle initial “S.” in his name especially due to Airport Security since his name is a very common name, etc), but I think I should stop at this point.

I hope that we have a great memorial event for him in the next SODA (SODA’17) the conference that he founded.

Rest in Peace David,

From Mohammad