Stuart has been part of the CS department at the University of Chicago since before they had a CS department and I knew Stuart well as a co-author, mentor, boss and friend during my 14+ years at Chicago. I would have attended this weekend no matter the location but a total eclipse a short drive from Atlanta (which merely had 97% coverage) certainly was a nice bonus.
Stuart Kurtz brought a logic background to computational complexity. He's played important roles in randomness, the structural properties of reductions, especially the Berman-Hartmanis isomorphism conjecture, relativization, counting complexity and logics of programs. I gave a talk about Stuart's work focusing on his ability to come up with the right definitions that help drive results. Stuart defined classes like Gap-P and SPP that have really changed the way people think about counting complexity. He changed the way I did oracle proofs, first trying to create the oracle first and then prove what happens as a consequence instead of the other way around. It was this approach, focusing on an oracle called sp-generic, that allowed us to give the first relativized world where the Berman-Hartmanis conjecture held.
Many thanks! I had a wonderful time, and it was great to get to hang out with so many colleague-friends.
ReplyDeleteJust a bit more about Stuart's scientific accomplishments:
ReplyDeleteBefore becoming a full-fledged, card-carrying CS person, Stu worked at the interface of Logic and Analysis. His definition of what is now called "Kurtz-random" became quite influential, as shown (for example) by the number of papers dealing with the property that come up in a google search.
Stuart was also instrumental in showing that much of the excitement in Theory circles about DNA computing was way too optimistic. While showing some approaches to be dead ends is perhaps not glamorous, complexity theorists know that it is very useful.
We also wrote a paper showing that the appropriate generalization of Collatz's "3n+1" puzzle is undecidable...
I am very sorry that logistics conspired against being at StuartFest.