<p>Sequential repetition can give you <strong>any</strong> 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.</p>

<p>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.</p>

<p><strong>Remark:</strong> 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.</p>

CC BY-SA 3.0
2011-09-24T19:51:41.393Z
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?
j.s.
CC BY-SA 3.0
2011-09-24T19:57:29.213Z
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.
Dana Moshkovitz
CC BY-SA 3.0
2011-09-24T19:17:18.683Z
2011-09-24T19:24:33.903Z
2011-09-24T19:24:33.903Z
Dana Moshkovitz
<p>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’$ :</p>

<ul>
<li>By constant number of applications of serial repetition: can get <strong>every</strong> constant s’>=1/2;</li>
<li>By constant number of applications of parallel repetition: can get <strong>every</strong> constant s’>0;</li>
<li>By $\theta(\log n)$ number of applications of Dinur’s gap amplification transformation: can get <strong>some</strong> constant $s’\geq1/2$; (see “<a href="http://www.cse.cuhk.edu.hk/~andrejb/pubs/pcpc.pdf" rel="nofollow">Gap Amplification Fails Below 1/2</a>”)</li>
</ul>

<p>My questions:</p>

<ol>
<li>Could you please correct me if I have made any mistakes?</li>
<li>What is special with ½ in serial repetition or Dinur’s transformation? why not another constant, like 1/3 or else?</li>
<li>Are such a results true for PCPs with imperfect completeness?</li>
</ol>

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

<cc.complexity-theory><pcp>
Effect of serial repetition on soundness of a PCP, and what is special with 1/2?
j.s.
# Effect of serial repetition on soundness of a PCP, and what is special with 1/2?

(Asked by: username_0 on 2011-09-24)

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](http://www.cse.cuhk.edu.hk/~andrejb/pubs/pcpc.pdf)”)

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.

**Tags:** cc.complexity-theory, pcp

---

## 1 answers

### Answer by username_1 on 2011-09-24. Score: 10 | Accepted answer

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:**
> **username_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 Raz’s parallel repetition theorem? Or why Raz’s theorem is so important?  
> **username_1**: 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.  

---

