[Lowerbounds, Upperbounds]

Every since I started giving talks, I wanted to know how my talks really were. But then, it seems difficult to collect the real opinions because of various reasons. (Diplomacy, friends, countrymen, comrades, etc.) For a start, I want to be able to conduct a thumbs-up/down vote as publicly as possible, but also preserves the secrecy of the votes.

Being at CMU actually makes this problem very easy to “solve”. All I did was to walk into a real crypto person in the corridor the very next morning. And before I finish telling my story, I am already presented with a proposal that is actually executable by real human beings. The trick is to have a way to distribute secret random bits.

Here is how one system may work to ask each person “Is this a good talk?”. At the door, each person is dealt with a card from a shuffled deck. Half of the cards in the deck have “This is a good talk” written underneath it, and the other half have “This is a bad talk”. That’s the secret bit for each person.

Two bins are placed at the door: “I agree” and “I disagree”. At the end of the talk, you just put the card (faced down, of course) into the appropriate bin. As long as your secret bit is not revealed, no one could be sure what your vote really was from observing which bin you used.

I can think of a number of ways to extend the number of questions asked in various ways, all involving secret initialization bits and XOR’ing with the answer bits.

So what questions do I want to ask? After asking around, it seems that the following questions are more interesting:

• Do you understand the problem statement?
• Do you think the problem is interesting?
• Do you understand the proposed solution in the high level?

This works better than pure thumbs-up/down because we may want to distinguish YNN from YYN.

I guess I will use it in my next talk and see how it goes.