BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Rational Proofs - Micali\, S (MIT)
DTSTART;TZID=Europe/London:20120410T143000
DTEND;TZID=Europe/London:20120410T153000
UID:TALK37385AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37385
DESCRIPTION:We unify the treatment of asymmetry of information
in theoretical computer science and economics.\nW
e put forward a new type of proof system\, where a
n unbounded Prover and a polynomial time Verifier
interact\, on inputs a string x and a function f\,
so that the Verifier may learn f(x). In our setti
ng there no longer are “good” or “malicious” Prove
rs\, but only RATIONAL ones. In essence\, (1) the
Verifier gives the Prover a reward in [0\,1] deter
mined by the transcript of their interaction\; (2)
the Prover wishes to maximize his expected reward
\; and (3) the reward is maximized only if the ver
ifier correctly learns f(x).\nRational proofs are
as powerful as interactive ones\, but can be amazi
ngly more efficient in the amount of communication
involved: that is\, the number of bits exchanged
and the number of rounds of interaction.\nJoint wo
rk with Pablo Azar.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR