MJD started off the session by asking people what they wanted to start with, since he had more slides than he could get through in 45 minutes. Everyone wanted to learn how to flip a coin over the telephone, so he proceeded to start in the middle, head for the end, and then jump back to the beginning again. That turned out not to be a bad thing, as he managed to fill in all the gaps pretty well.
He spent some time talking about remote coin flipping, and subsequently remote proof of knowledge without revealing anything about said knowledge. I’m afraid I’d mangle the details if I tried to relate them, but the protocols are interesting and actually fairly easy to understand. Someone in the audience even suggested an improvement for MJD’s remote coin-flip protocol.
MJD then spent a nice chunk of time on various hard problems, discussing the concepts of NP, NP-complete, undecideable, and so on. For examples he used Hamiltonian Cycles, the Knapsack Problem, and the Halting Problem. He gave a very interesting specific case that shows just how subtle the Halting Problem can be: Start with a number N; if it is even, divide it in half; if it is odd, multiply by 3 and add 1; repeat until N is 1. Noone knows if this code is guaranteed to halt for all natural numbers.
There’s no way I could do this talk (or topic) justice here, so let me simply say that it’s a fun way to spend an hour if you get a chance at a future conference.
What’s your favorite hard problem?