[My Computational Complexity Web Log] Walter Savitch
After the FCRC meetings I attended were concluded, I headed up to UCSD for the celebration of Walter Savitch for his sixtieth birthday and upcoming retirement. He gained his fame in complexity for Savitch's Theorem that shows "P=NP" for space.
I learned quite a bit at the meeting. Walt Savitch was Steve Cook's first student, his only student while Cook was at Berkeley in his pre-Toronto pre-"SAT is NP-complete" days. Also as Cook said, Savitch is the only student he has had with a theorem named after him. That theorem made up a good part of Savitch's Ph.D. thesis. At the celebration Cook gave an overview on propositional proof systems.
After coming to UCSD, Savitch did some work on computational linguistics and one of the leaders of the field, Aravind Joshi, gave a talk on combining trees to keep the structure when parsing sentences.
Savitch is probably best known now in computer science for his textbooks in introductory programming that likley many of you have used.