I gave a talk on Communication Complexity (slides are here) where I did the following:
- I stated the problem: Alice has x, Bob has y, both strings of length n. They want to know if x=y without too much communication.
- I noted that they can easily solve this with n+1 bits of communication and raised the question of Can They Do Better?
- We discussed this. Someone mentioned average case (informally), which helped me clarify the problem. Someone else suggested sending the number-of-1's and if it didn't match they weren't equal, but also noted that if they did--- weren't sure. Most thought that one COULD do better or else I wouldn't be talking about it.
- I tell them that NO you can't do better (I do not prove this).
- I told them about mod arithmetic and how in mod p, p a prime, poly of degree d have at most d roots.
- I presented the O(log n), error 1/n, randomized protocol for equality that uses polynomials mod p.
- I briefly talked about comm complexity in general.
MOM: Alice and Bob-- are they married?
BILL: Oh. I'll say no.
MOM: If they are not married then how come they have such a hard time communicating?
DAD: (he didn't say anything but I could tell he agreed).