# 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?

• Can you explain why you suspect there is a relation between them? – Kaveh Dec 8 '15 at 0:33
• my suspicion comes from drops.dagstuhl.de/opus/volltexte/2011/3320/pdf/2.pdf and also it seems one could cook up graph structures with closed paths corresponding to monomials or monomials with linear transformation of variables. – T.... Dec 8 '15 at 1:17

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.
• 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? – T.... Dec 8 '15 at 5:32
• 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). – Joshua Grochow Dec 8 '15 at 5:57