What better way to procrastinate than to hear an Australian radio show interview me about the quantum query complexity of the collision problem, public-key cryptography, interactive proofs, computational intractability as a law of physics, and my great love for my high school? The first part of the program is about Australia’s population of cane toads (or rather, “tie-oads”). Then at 32:40, they start in with a report on the FQXi conference in Iceland, and interviews with Max Tegmark, Fred Adams, and Simon Saunders. I’m from 39:10 to 46:50.
A few comments/corrections:
- The interviewer, Pauline Newman, asks me about the practical implications of the collision lower bound, and then cuts to me talking about how quantum computers could break the RSA cryptosystem. Of course, the connection is only an indirect one (the collision lower bound is what gives hope that one could design collision-resistant hash functions that, unlike RSA, are secure even against quantum attacks).
- I said that, when trying to solve jigsaw puzzles or schedule airline flights, there doesn’t seem to be anything one can do that’s fundamentally better than trying every possibility. I should have added, “in the worst case.”
- The reason I mentioned how old I was when IP=PSPACE was proved is not that I’m a narcissist (though I am), but because in a section that was cut, Pauline asked me if I proved IP=PSPACE, and I was trying to make it clear that I didn’t. The theorem was proved by Shamir, building on work of Lund, Fortnow, Karloff, and Nisan.
- Pauline’s assertion that I “took off on a snowmobile without [my] passenger” and “left a distinguished physicist stranded on a glacier” is a gross exaggeration. What happened was, I waited and waited for someone — anyone — to climb onto my snowmobile. When no one did (maybe because everyone was scared by my abysmal driving ability), I figured I should just go.
Anyway, at least the um’s and uh’s seem to have been under control, compared to my interview with Lance two years ago.