Two polynomials $f,g$ are isomorphic iff $f(x\_1,\ldots x\_n)=g(\pi(x\_1, \ldots x\_n))$ for a permutation $\pi$.


$f,g$ are equivalent if there exists invertible linear transormation
$A$ such that $f(X)=g(A\cdot X)$.


Assume $f,g$ are quadratic.


[Paper](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Poly20Equiv.pdf) p.1 claims that equivalence 
of quadratic polynomials is efficient via reduction to sum of squares.



> 
> What is the complexity of isomorphism of quadratic polynomials?
> 
> 
> 



Complexity of quadratic polynomials isomorphism
It is equivalent to (coloured) graph isomorphism problem. 


To see this,
one writes $f(X)=X^\top A\_f X$ for $A\_f$ a symmetric $n\times n$ matrix. Then $f$ and $g$ are isomorphic if $\pi A\_f \pi^\top=A\_g$ for a permutation $\pi$. To see it is also only if, suppose $f(X)=g(\pi(X))$, but $A':=\pi A\_f \pi^\top\not=A\_g=:A$. If $A'\_{ii}\neq A\_{ii}$ then $f(X\_i)\neq g(\pi (X\_i))$, a contradiction. If $A'\_{ij}\neq A\_{ij}$ for $i\neq j$ then $$f(X\_i+X\_j)-g(\pi(X\_i)+\pi(X\_j))=2A'\_{ij}X\_iX\_j-2A'\_{ij}(\pi(X\_i))(\pi(X\_j))=2A'\_{ij}X\_iX\_j-2A\_{ij}X\_iX\_j,$$
again a contradiction. therefore the isomorphism of $f$ and $g$ is equivalent to isomorphism of coloured graphs with adjacency matrices $A\_f$ and $A\_g$.


