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
    The way things happened, Irit was inspired by Omer's proof when she came up with the PCP proof. – Dana Moshkovitz Sep 19 '12 at 13:48
up vote 12 down vote accepted

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: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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