His thesis was in Kolmogorov complexity. One particularly neat trick from his thesis: A PRG that under reasonable assumptions maps strings of length O(log n) to strings of length 2^O(n), a double exponential jump done by combining two PRGs based on Nisan and Wigderson.
I love doing these defenses outside the US. We got to dress like monks when quizzing the defendant. After the defense we had a wonderful lunch with Port Wine from Porto of course.
|Andre the Defender|
|The Jury: Harry Buhrman, Luis Antunes, me and Armando Matos|