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?


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), 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.

Comments (5)

  • +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  
  • +0 – Does representation matrix need to be polynomial sized? How else could we feed input to problem (like any other decision problem)? — Dec 08, 2015 at 06:06  
  • +0 – I am trying to find details here but I am unable to… — Dec 08, 2015 at 06:12  
  • +1 – @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.) — Aug 08, 2016 at 05:40  

External Links

External links referenced by this document: