Summer 2015

Sequential Composition of Rational Proofs

Monday, June 8th, 2015 4:15 pm4:40 pm

Add to Calendar


Calvin Lab Auditorium

We show that Rational Proofs do not satisfy basic compositional properties in the case where a large number of "computation problems" are outsourced. We show that a "fast" incorrect answer is more remunerable for the prover, by allowing him to solve more problems and collect more rewards. We present an enhanced definition of Rational Proofs that removes the economic incentive for this strategy and we present a protocol that achieves it for the case of uniform bounded-depth circuits.

Joint work with Matteo Campanelli (CUNY))