Theoretical Computer Science
graph-isomorphism derandomization
Updated Thu, 16 Jun 2022 04:39:18 GMT

# Connections between Graph Isomorphism and Polynomial Equivalence

Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?

In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards derandomization of Polynomial Identity Testing?

## Solution

For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq and RingIso are relatively close to one another, and RingIso is as hard as integer factoring...)

Note that equivalence problems in general tend to be nontrivially harder than their specific instances or testing for triviality. For example, Formula Isomorphism is believed to be intermediate between the first two levels of $\mathsf{PH}$, although testing isomorphism to the trivial formula is $\mathsf{coNP}$-complete. (This is the Boolean analogue of your suggestion of trying to use PolyEq to solve PIT. Of course, one could argue that our intuition for the intermediate status of Formula Iso is largely based on Graph Iso...) As another example, testing for Knottedness is in $\mathsf{NP} \cap \mathsf{coNP}$ (assuming GRH; albeit only recently), but the current best upper bound on testing Knot Equivalence is that it can be done in time that is a tower of 2's of height $c^n$, where $n$ is the number of crossings and $c = 10^{10^6}$ (see here). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems significantly harder than the former.

• +0 – Thank you for the detailed post. Is there a matrix theoretic framework for Knot equivalence analogous to $A=PBP'$ ($A,B$ adjacency matrices of isomorphic graphs with $P$ permutation) framework for graph equivalence? — Dec 08, 2015 at 05:32
• +0 – Not as far as I know, at least not with reasonably-sized matrices. Note that if A is $N \times N$, then most natural problems of the form you describe can be decided in $2^{O(N^2)}$ time using quantifier elimination over $\mathbb{R}$, which is much better than the current best upper bound for KnotEq (unless $N$ itself is gigantic). — Dec 08, 2015 at 05:57