<p>The paper you linked in the comments - and references therein - already seems to answer your first question. </p>

<p>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...)</p>

<p>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 <a href="http://arxiv.org/abs/1112.0845" rel="nofollow noreferrer">only recently</a>), 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 <a href="https://cstheory.stackexchange.com/a/30625/129">here</a>). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems <em>significantly</em> harder than the former.</p>

CC BY-SA 3.0
2015-12-08T05:32:19.707Z
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?
Turbo
CC BY-SA 3.0
2015-12-08T05:57:33.723Z
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
CC BY-SA 3.0
2015-12-08T06:06:00.957Z
Does representation matrix need to be polynomial sized? How else could we feed input to problem (like any other decision problem)?
Turbo
CC BY-SA 3.0
2015-12-08T06:12:46.663Z
I am trying to find details here but I am unable to https://www.math.hmc.edu/seniorthesis/archives/2006/jmay/jmay-2006-thesis.pdf
Turbo
CC BY-SA 3.0
2016-08-07T13:54:22.730Z
how are knots represented on a turing machine then in poly space?
Turbo
CC BY-SA 3.0
2016-08-08T05:40:44.193Z
@Turbo: One way is by a 4-valent graph with each vertex endowed with the data of over-and-under crossings (the knot diagram). However, note that equivalence between knots with this input format isn't phrased in the way you describe, for example because two knots with different numbers of crossings can be equivalent. (Alternately, you can represent a knot by a piecewise-linear knot with rational - or even integer, I think - coordinates in Euclidean 3-space.)
Joshua Grochow
CC BY-SA 3.0
2015-12-08T05:08:42.003Z
2015-12-08T05:08:42.003Z
2017-04-13T12:32:28.053Z
Joshua Grochow
<p>Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?</p>

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

CC BY-SA 3.0
2015-12-08T00:33:44.777Z
Can you explain why you suspect there is a relation between them?
Kaveh
CC BY-SA 3.0
2015-12-08T01:17:06.173Z
my suspicion comes from http://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.
Turbo
<graph-isomorphism><derandomization>
Connections between Graph Isomorphism and Polynomial Equivalence
Turbo
# Connections between Graph Isomorphism and Polynomial Equivalence

(Asked by: username_0 on 2015-12-07)

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?

**Tags:** graph-isomorphism, derandomization

> **Comments:**
> **username_1**: Can you explain why you suspect there is a relation between them?  
> **username_0**: my suspicion comes from http://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.  

---

## 1 answers

### Answer by username_2 on 2015-12-08. Score: 10 | Accepted answer

The paper you linked in the comments - and references therein - already seems to answer your first question.

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](http://arxiv.org/abs/1112.0845)), 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](https://cstheory.stackexchange.com/a/30625/129)). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems *significantly* harder than the former.

> **Comments:**
> **username_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?  
> **username_2**: 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).  
> **username_0**: Does representation matrix need to be polynomial sized? How else could we feed input to problem (like any other decision problem)?  
> **username_0**: I am trying to find details here but I am unable to https://www.math.hmc.edu/seniorthesis/archives/2006/jmay/jmay-2006-thesis.pdf  
> **username_0**: how are knots represented on a turing machine then in poly space?  
> **username_2**: @username_0: One way is by a 4-valent graph with each vertex endowed with the data of over-and-under crossings (the knot diagram). However, note that equivalence between knots with this input format isn't phrased in the way you describe, for example because two knots with different numbers of crossings can be equivalent. (Alternately, you can represent a knot by a piecewise-linear knot with rational - or even integer, I think - coordinates in Euclidean 3-space.)  

---

