various fundamental questions in arithmetic complexity can be re-interpreted as particular instances of [`PolyProj`]{}(see [@DBLP:conf/coco/Burgisser12; @DBLP:conf/stoc/Kayal12; @DBLP:journals/cacm/Mulmuley12; @DBLP:journals/siamcomp/MulmuleyS01]).

Typically, the famous <span style="font-variant:small-caps;">VP</span> vs <span style="font-variant:small-caps;">VNP</span> question ([@DBLP:journals/tcs/Valiant79]) can be formulated as an equivalence problem between the determinant and permanent polynomials. Such a link is in fact the core motivation of Geometric Complexity Theory. The problem of computing the symmetric rank ([@DBLP:journals/jsc/BernardiGI11; @DBLP:journals/siammax/ComonGLM08]) of a symmetric tensor also reduces to an equivalence problem involving a particular multivariate polynomial ([@DBLP:conf/stoc/Kayal12]). To mention another fundamental problem, the task of minimizing the cost of computing matrix multiplication reduces to a particular equivalence problem ([@DBLP:conf/stoc/BurgisserI11; @DBLP:conf/stoc/BurgisserI13; @DBLP:conf/soda/CohnU13; @DBLP:conf/stoc/Kayal12]).

Organization of the Paper and Main Results {#organization-of-the-paper-and-main-results .unnumbered}
------------------------------------------

Let ${{\mathbb}{K}}$ be a field, ${{\mathbf}{f}}$ and ${{\mathbf}{g}}$ be two sets of $m$ polynomials over ${{\mathbb}{K}}[x_1,\ldots,x_n]$. The Isomorphism of Polynomials ([`IP`]{}) problem, introduced by Patarin ([@DBLP:conf/eurocrypt/Patarin96]), is as follows:\
**Isomorphism of Polynomials ([`IP`]{})**\
**Input:** $\big( ({{\mathbf}{f}}=(f_1,\ldots,f_m)$ and ${{\mathbf}{g}}=(g_1,\ldots,g_m)\big) \in {{\mathbb}{K}}[x_1,\ldots,x_n]^m \times {{\mathbb}{K}}[x_1,\ldots,x_n]^m$.\
**Question:** Find – if any – $(A,B) \in\operatorname{GL}_n({{\mathbb}{K}}) \times
\operatorname{GL}_m({{\mathbb}{K}})$ such that: $${{\mathbf}{g}}({{\mathbf}{x}})=B\cdot {{\mathbf}{f}}(A \cdot {{\mathbf}{x}}), \mbox{ with
  ${{\mathbf}{x}}=(x_1,\dots,x_n)^{\operatorname{T}}$}.$$ While [`IP`]{}is a fundamental problem in multivariate cryptography, there are quite few algorithms, such as [@DBLP:conf/eurocrypt/PatarinGC98; @DBLP:conf/eurocrypt/BouillaguetFV13; @FaugerePerret06], solving [`IP`]{}. In particular, [@FaugerePerret06] proposed to 