Theoretical Computer Science
cc.complexity-theory pcp
Updated Thu, 23 Jun 2022 19:02:39 GMT

# Effect of serial repetition on soundness of a PCP, and what is special with 1/2?

As far as I know, following operations convert a $PCP_{1,s}[O(\log n),O(1)]$ , to a $PCP_{1,s}[O(\log n),O(1)]$, with following $s$ :

• By constant number of applications of serial repetition: can get every constant s>=1/2;
• By constant number of applications of parallel repetition: can get every constant s>0;
• By $\theta(\log n)$ number of applications of Dinurs gap amplification transformation: can get some constant $s\geq1/2$; (see Gap Amplification Fails Below 1/2)

My questions:

1. Could you please correct me if I have made any mistakes?
2. What is special with in serial repetition or Dinurs transformation? why not another constant, like 1/3 or else?
3. Are such a results true for PCPs with imperfect completeness?

remark: with $PCP_{c,s}$, I mean PCP with completeness c and soundness error s.

## Solution

Sequential repetition can give you any constant soundness error larger than 0, not just soundness error $\geq 1/2$. Dinur's approach gives you a constant soundness error which is not only at least half, but, in fact, extremely close to 1, maybe 0.99999. The note of Andrej Bogdanov that you linked to shows that getting a soundness error smaller than half inherently won't work using Dinur's approach. The reason is specific to this approach, and is explained well in the note.

The soundness amplification results work for imperfect completeness as well. It's pretty straightforward to convince yourself of that in the case of sequential/parallel repetition. Dinur's approach can also be adapted to imperfect completeness.

Remark: Dinur's approach, just like the other two approaches, requires a number of iterations/repetitions that depends on the soundness you start with and the soundness you want to get. In her case it's $\Theta(\log(\frac{1}{1-s}))$ iterations to get to constant soundness. Irit starts with $s\approx 1-\frac{1}{n}$, and that's why she needs $\Theta(\log n)$ iterations.