In the degree reduction step of Dinur's proof, the input graph $G$ is transformed into a graph $G'$ by replacing each vertex $v \in V(G)$ by a set of vertices, $cloud(v)$, such that $|cloud(v)| = degree_G(v)$, and imposing a degree d expander graph on $cloud(v)$ for all $v \in V(G)$. This makes $G'$ a d+1 regular graph, and the construction ensures that the gap reduces only by a constant factor. I was wondering what would happen if we impose a cycle on each cloud instead? I tried bounding the drop in the gap, but was not able to do so. So, does the proof break down at this step?


1 Answer 1


It is essential to the construction to have an expander between the copies of a vertex (the "cloud" of the vertex). Otherwise, you won't be able to argue that the adversary assigning values to the vertices is better off assigning those vertices the same value.

In particular, if instead of an expander you have a cycle, the prover can assign one half-cycle one value, and the other half-cycle another value. This way with good probability the verifier won't catch the inconsistency between the vertices, but you can't appeal to the soundness of the original graph to prove soundness for the new graph (it's like allowing the prover in the original graph to use two different assignments for the vertex).

  • $\begingroup$ So, the argument precisely fails at this point since we can't control the soundness parameter or the gap (using the soundness parameter for the original graph)? $\endgroup$
    – user1694
    Jun 16, 2011 at 16:35
  • 2
    $\begingroup$ @Abhishek: controlling the soundness parameter for the new graph is how you control the gap (= gap between completeness and soundness, and completeness does not change in the new graph). Think of an expander as a small-degree approximation of a complete graph: a complete graph would force you to use the same assignment for all vertices. $\endgroup$ Jun 16, 2011 at 16:56
  • 2
    $\begingroup$ @Abhishek: yes. $\endgroup$ Jun 16, 2011 at 17:30
  • $\begingroup$ @Abhishek if this answer is what you're looking for (and it seems like it is) you should click on the check-mark below the answer score to accept it. $\endgroup$ Jun 21, 2011 at 21:23

Your Answer

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