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.

Comments (2)

  • +0 – thanks for your great answer. Dana, one thing is obscure to me: if we can get arbitrary positive constant soundness by constant application of sequential repetition, then why we need Razs parallel repetition theorem? Or why Razs theorem is so important? — Sep 24, 2011 at 19:51  
  • +2 – For hardness of approximation you usually need what's called "a two query projection PCP", meaning that the verifier makes two queries, and the value of the first determines the value of the second. Parallel repetition preserves this structure while decreasing the error (and it's very easy to get this structure from standard PCP Theorems when the error is high). That's why Ran's Theorem is so important. Ran and I also have a construction of two query projection PCP with sub-constant error and almost-linear proof length which is based on sequential repetition and algebra. — Sep 24, 2011 at 19:57  

External Links

External links referenced by this document:

References