Wednesday, March 03, 2010
Congratulations to David Johnson, Knuth Prize Winner
I'm pleased to hear that David Johnson has won the Knuth Prize for "his contributions to theoretical and experimental analysis of algorithms." David has done a great many wonderful things, but I thought I'd highlight something that I imagine is underappreciated today, his book Computers and Intractability: A Guide to the Theory of NP-Completeness. We're a bit spoiled these days, what with Wikipedia pages with lists of NP-complete problems and online compendiums with references. But in ye olden days, when I was a grad student, if you had a reduction you needed to ponder, you went to Garey and Johnson. The book was an inspiration, and an invaluable research resource, to many. It's one of the most cited (the most cited?) references in computer science, and the book will rightly hold a special place in the history of computer science.