Recently Added

Better Pseudorandom Generators from Milder Pseudorandom Restrictions

Parikshit Gopalan
Microsoft Research Silicon Valley, Mountain View, CA
April 3, 2012

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs that achieve near-optimal seed-length even in the low error regime.

Rational Proofs

Pablo Azar
Massachusetts Institute of Technology
April 2, 2012

We study 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)$. The novelty of our setting is that there no longer are ``good" or ``malicious" provers, but only rational ones. In essence, the Verifier has a budget $c$ and gives the Prover a reward $r \in [0,c]$ determined by the transcript of their interaction; the prover wishes to maximize his expected reward; and his reward is maximized only if he the verifier correctly learns $f(x)$.