Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Walter Savitch

Expand Messages
  • Lance Fortnow
    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.
    Message 1 of 1 , Jun 18, 2003
    • 0 Attachment
      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.

      Congrats Walt on a fine career and here's hoping retirement doesn't slow you down.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 6/18/2003 8:16:48 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.