May 31, Tuesday
12:00 – 14:00
If I don't know you, and you want your e-mail to appear in my inbox, then you must attach to your message an easily verified "proof of computational effort", just for me and just for this message.
To apply this approach one needs to be able to come up with computational problems where solving them requires significant expenditure of resources while verifying a solution can be done easily. In this talk I will introduce this approach and concentrate on the choice of computational problems for which most of the work is in retrieving information from memory. In particular I will describe the connection to pebbling problems.
The talk is based on two papers:
Cynthia Dwork, Andrew Goldberg and Moni Naor: On Memory-Bound Functions for Fighting Spam.
Cynthia Dwork, Moni Naor and Hoeteck Wee: Pebbling and Proofs of Work