# Is there a gap amplification type of result for the Graph Isomorphism Problem?

Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, if there is a permutation $\Pi$ such that $(i,j)$ is an edge in $G_1$ if and only if $(\Pi(i),\Pi(j))$ is an edge in $G_2$. The Graph Isomorphism Problem is the problem of deciding whether two given graphs are isomorphic.

Is there an operation on graphs that produces "gap amplification" in the style of Dinur's proof of the PCP Theorem? In other words, is there a polynomial time computable transformation from $(G_1,G_2)$ to $(G'_1,G'_2)$ such that

• if $G_1$ and $G_2$ are isomorphic, then $G'_1$ and $G'_2$ are also isomorphic, and
• if $G_1$ and $G_2$ are not isomorphic, then for each permutation $\Pi$, the graph $G'_1$ is "$\epsilon$-far" from $\Pi(G'_2)$ for some small constant $\epsilon$, where $\epsilon$-far means that if we choose $(i,j)$ uniformly at random, then with probability $\epsilon$ either
• $(i,j)$ is an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is not an edge of $G'_2$, or
• $(i,j)$ is not an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is an edge of $G'_2$.
• @domotorp: “Polynomial-time transformation” is a standard terminology to refer to a deterministic polynomial-time Turing machine whose input and output are both strings. In this case, this Turing machine takes pair (G1, G2) as input and produces pair (G′1, G′2) as output. Each graph is encoded as an adjacent matrix, for example. Nov 25, 2011 at 15:27
• I thought the PCP theorem was valid for any NP problem, so in particular it should hold for Graph Isomorphism ? May 12, 2012 at 18:01
• @dkuper The author means to ask if there is a gap-amplifying reduction which reduces instances of graph isomorphism to instances of graph isomorphism with a bigger gap; he is not asking about the PCP Theorem directly, just about a technique used in proving hardness of approximation... Sep 26, 2012 at 22:31
• Probably a long shot, but could you show that if this were the case, then you could solve graph isomorphism in quantum polynomial time? Nov 3, 2012 at 17:43
• It is consistent with current state of knowledge that even SAT has linear time algorithm so what you have written seems unlikely to be known. If it is please add a reference to your answer. Nov 14, 2013 at 22:47