The Randomness Complexity of Parallel Repetition

**Kai-Min Chung**

**
**

**M****onday September 26, 2011 **

4:00 PM,
5130 Upson Hall

__Abstract:__

#### 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.