Toads, lower bounds vie for control of Australia
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.
Follow
Comment #1 August 18th, 2007 at 11:40 pm
Cane toads are incredible! They’re huge, ugly, and poisonous — everything that Australia could want in a foreign invasive pest species. Best of all, they were introduced deliberately.
Comment #2 August 19th, 2007 at 12:12 am
On the other hand, unless I see a better explanation somewhere, “multiverses” are a silly non-idea and aren’t nearly as interesting as cane toads.
I more-or-less agree with Lawrence Krauss at the end of the interview. Especially after enduring the discussion of “multiverses”, I would say that dwelling too long on “deep” questions in science amounts to eating icing without the cake. I think that Krauss can be too skeptical of abstractions, but in this context he’s right. Unfortunately his position was coopted, both by the radio program and FQXi itself, as yet more philosophizing about “deep” questions!
I liked your segment of the radio program, Scott, because you talked about tangible results in computer science which withstand Krauss’ wise objection. Unfortunately, a lot of TCS ideas whizzed by very quickly. You would have made a better impression if they had given you an hour to discuss what was crammed into less than 8 minutes. Or they could have cut down the number of topics.
Comment #3 August 19th, 2007 at 7:28 pm
Very nice. I enjoyed that, Scott.
Comment #4 August 19th, 2007 at 8:24 pm
Thanks!
Comment #5 August 19th, 2007 at 8:35 pm
It is unlikely that you’re related to him, but sometimes when I read your name, I think of a friend of mine, who entered Caltech the same year as I, and whom I several times visited after he graduated, on both coasts of the USA. His death was the most bizarre of anyone I knew personally.
http://en.wikipedia.org/wiki/Marc_Aaronson
Comment #6 August 20th, 2007 at 2:40 pm
Scott writes:
You may have just answered your own question.
Comment #7 August 21st, 2007 at 7:28 am
I hope that the caltech crowd doesn’t introduce those poisonous toads to the area around MIT.