Talks
Fall 2015

# Human Computation

Monday, Sep. 28, 2015 9:30 am10:15 am PDT

Does there exists a family H of hash functions h with the property that

1.  Any h in H is humanly computable: a human can select a random h∈H, then
- (preprocessing time) learn to compute h in at most a few (≤ 3?) hours, and thereafter
- (processing time) take at most 1 minute per input x_i to compute h(x_i),

but

2.  NO  ADVERSARY -- BE IT HUMAN, COMPUTER, OR COMBINATION OF THE TWO -- that
- knows the family H but not which particular h was chosen, and
- observes (just) enough pairs (x1, h(x1)), (x2, h(x2)), (x3, h(x3)), ... (for randomly chosen x1, x2, x3, ...) to completely specify h, can (with nontrivial probability) compute h(x) on a new randomly chosen x.

This talk will deal with this question for humans that compute h in their heads matched against a powerful human + supercomputer (10¹⁸ instructions per second) adversary.  The adversary wins in the first round, Q, at which it correctly guesses h(x) for a new randomly chosen x.