4
$\begingroup$

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 Dinur’s 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 Dinur’s 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 Raz’s parallel repetition theorem? Or why Raz’s theorem is so important? $\endgroup$
    – j.s.
    Sep 24, 2011 at 19:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dana Moshkovitz
    Sep 24, 2011 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.