The Randomness Complexity of Parallel Repetition
Monday September 26, 2011
5130 Upson Hall
Consider a $m$-round interactive protocol with soundness error $1/2$. How much extra randomness is required to decrease the soundness error to $\delta$ through parallel repetition? Previous work, initiated by Bellare, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, $m \cdot O(\log (1/\delta))$ bits of extra randomness suffices. In this work, we initiate a more general study of the above question.
- We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with *computational soundness* (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting.
- We show that obtaining even a sub-linear dependency on the number of rounds $m$ (i.e., $o(m) \cdot \log(1/\delta)$) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting.
- We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting.
These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.
This is a joint work with Rafael Pass.