Talks
Fall 2015

Human Computation

Monday, September 28th, 2015 9:30 am10:15 am

Add to Calendar

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. 
 
Human computability has numerous applications including CAPTCHAS and humanly computable passwords.