<p>The precise answer to your question is given by Oded Goldreich in his article &quot;Bravely, Moderately: A Common Theme in Four Recent Works&quot;.</p>
<p>Here is the link: <a href="https://www.wisdom.weizmann.ac.il/%7Eoded/p_brave.html" rel="nofollow noreferrer">https://www.wisdom.weizmann.ac.il/~oded/p_brave.html</a></p>

CC BY-SA 4.0
2012-09-18T14:14:07.363Z
2024-03-03T10:38:14.833Z
2024-03-03T10:38:14.833Z
Mahdi Cheraghchi
<p>The book by Arora and Barak contains in chapter notes on PCP</p>

<blockquote>
  <p>We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's deterministic logspace algorithm for undirected connectivity described in Chapter 20, which suggests that more connections are waiting to be made between these different areas of research. (pg 494)</p>
</blockquote>

<p>What precisely is meant by this reminiscence? Is there a common property/lemma than can be "factored out" of these two proofs?</p>

CC BY-SA 3.0
2012-09-19T13:48:50.467Z
The way things happened, Irit was inspired by Omer's proof when she came up with the PCP proof.
Dana Moshkovitz
<cc.complexity-theory><space-bounded><pcp>
Connection between PCP and L=SL
sdcvvc
# Connection between PCP and L=SL

(Asked by: username_0 on 2012-09-18)

The book by Arora and Barak contains in chapter notes on PCP

> We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's deterministic logspace algorithm for undirected connectivity described in Chapter 20, which suggests that more connections are waiting to be made between these different areas of research. (pg 494)

What precisely is meant by this reminiscence? Is there a common property/lemma than can be "factored out" of these two proofs?

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

> **Comments:**
> **username_1**: The way things happened, Irit was inspired by Omer's proof when she came up with the PCP proof.  

---

## 1 answers

### Answer by username_2 on 2012-09-18. Score: 14 | Accepted answer

The precise answer to your question is given by Oded Goldreich in his article "Bravely, Moderately: A Common Theme in Four Recent Works".

Here is the link: [https://www.wisdom.weizmann.ac.il/~oded/p\_brave.html](https://www.wisdom.weizmann.ac.il/%7Eoded/p_brave.html)


---

