Super-Efficient Rational Proofs
Speaker: Pablo Azar, CSAIL, MIT
Date: Friday, December 14 2012
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
A rational proof is an interactive proof where the prover, Merlin, is neither honest nor malicious, but rational. That is, Merlin acts in order to maximize his own utility. Rational proofs have been previously studied when the verifier, Arthur, is a probabilistic polynomial-time machine.
In this paper, we characterize {\em super efficient rational proofs}, that is, rational proofs where Arthur runs in $O(\log n)$ time. Specifically,
1. If Merlin can send a polynomial-length proof to which Arthur has random access, then the set of languages having a super efficient rational proof with one round of interaction is $P^{||NP}$, the set of languages decidable by a polynomial time machine that can ask non-adaptive queries to $NP$.
2. If Merlin is limited to send a proof of length $O(\log n)$, then the set of languages having a super efficient rational proof is uniform $TC^0$.
Our new rational proofs are very practical. Not only are they much faster than their classical analogues, but they also provide very tangible incentives for the expert to be honest. Arthur only needs a polynomial-size budget, yet he can penalize Merlin by a large quantity if he deviates from the truth.
See other events that are part of CIS Seminars 2012/2013
See other events happening in December 2012
