Title:	Spam fighting and The Complexity of Pebbling Graphs
Date:	May 8, 2006 (Monday)
Time:	11:00 a.m. - 12:00 noon
Venue:	Room 1027, 10/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker:	Mr. Hoeteck Wee PhD candidate The University of California, Berkeley USA

ABSTRACT:

Consider the following simple technique for combatting spam:

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.

Joint work with Cynthia Dwork (Microsoft Research, USA) and Moni Naor (Weizmann Institute of Science, Israel)

BIOGRAPHY:

Hoeteck Wee is a graduate student at University of California, Berkeley, under the supervision of Luca Trevisan. The above-mentioned work was performed while he was a summer intern at Microsoft Research, Silicon Valley Campus. He is currently a visiting student at Tsinghua University in Beijing.

Enquiries: Miss Temmy So at tel 2609 8444

For more information, please refer to http://www.cse.cuhk.edu.hk/seminar