Rational Proofs
Speaker: Silvio Micali , CSAIL, MIT
Date: May 11 2012
Time: 10:30AM to 12:00PM
Location: Hewlett Room, 32-G882, Stata Center, MIT
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
We unify the treatment of asymmetry of information in theoretical
computer science and economics.
We put forward a new type of proof system, where an 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 setting there
no longer are “good” or “malicious” Provers, but only RATIONAL
ones. In essence, (1) the Verifier gives the Prover a reward in [0,1]
determined by the transcript of their interaction; (2) the Prover
wishes to maximize his expected reward; and (3) the reward is
maximized only if the verifier correctly learns f(x).
Rational proofs are as powerful as interactive ones, but can be
amazingly more efficient in the amount of communication involved: that
is, the number of bits exchanged and the number of rounds of
interaction.
Joint work with Pablo Azar.
See other events that are part of CIS Seminars 2011/2012
See other events happening in May 2012
