Thursday, August 24, 2017
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.