9
$\begingroup$

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?

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

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$

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.