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?

  • 4
    $\begingroup$ The way things happened, Irit was inspired by Omer's proof when she came up with the PCP proof. $\endgroup$ Commented Sep 19, 2012 at 13:48

1 Answer 1


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


Your Answer

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

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