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).

Bob is married to Eve, and having an affair with Alice. The more involved scenario has Darth being secretly in love with Eve and trying to sabotage this illicit liaison between Alice and Bob to improve Eve's quality of life. Simple. (Not sure how well your parents will approve of your working in such a field if you tell them this, though!)

ReplyDelete