[Computational Complexity] Today is Knuth's 70th birthday!!
- Today, January 10, is Donald Knuth's 70th birthday. I have some thoughts on Knuth, but I am sure that my readers have more. So, I'm asking you to leave comments on Donald Knuth. Let's break the record for number-of-comments on an entry. Knuth deserves it! (What is the record? If I were as meticulous as Knuth I would know.)
- My first exposure to Knuth's work was in 1980 when I was doing a survey on Factoring Polynomials over Finite Fields. I couldn't find the relevant papers in the library (I can hear people under 25 saying weren't they on line? or what's a library?), so I was told to look in Knuth Volume 2. And indeed, there was a wonderful exposition of what I needed to know, and the history behind it. Quite scholarly and, unfortunately, quite rare among other researchers.
- Browsing through Knuth's volume I got the impression that his attitude is I want to solve problem X and I'll use whatever math I need to solve it, even if I have to develop it myself. Never shy away from a problem because you don't know the math needed, or even because the math you need hasn't been developed yet.
- TeX: Reading the TeX manual you actually learn things of interest outside of TeX. Not only did I learn how to hyphenate in TeX, I also learned that in German when you hyphenate some words, you actually change their spelling. And, of course, TeX can handle this.
- TeX and LaTeX: Revolutionized how we write papers. Facilitated the notion of keeping papers on line for easy access.
- First Contact!: I got a postcard from Knuth pointing out an error in a paper I wrote. WOW! a postcard from Knuth.
- Second Contact!: Knuth asks me to get a review of Volume 4 in my book review column. I was surprised that he emailed me (he does not use email) and amazed that Volume 4 was coming out. The way he asked me was interesting: seethis post
- I always thought Volume 4 was a myth, like the missing part of the Dead Sea scrolls. How long has the world been waiting for Volume 4? Knuth needed a term for what we know as `NP-completeness' for use in Volume 4. He held a contest, and NP-completeness won. (He ended up not using it in Volume 4.)
- Volume 4: Yes, it really is out, sort of. It's coming out as a series (or a sequence) of fascicles (small books) of (I am not making this up) exactly 128 pages. It's on generation of combinatorial objects. The second fascicle, on enumerating all strings of length n, (e.g., Gray codes) is fascinating. Includes history and the needed mathematics. History goes back to the mid 1850's. Quite scholarly and, unfortunately, quite rare among other researchers.
- What has Knuth's influence been on computer science? He was one of the first people to realize that an algorithm can be analysed in a mathematical and intelligent way without running it. This is one of the most important starting points for computer science theory. Perhaps even for computer science.
Posted By GASARCH to Computational Complexity at 1/10/2008 09:58:00 AM