An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable of $g$ by an affine combination of the variables occurring in $f$, then it is said to be an affine projection of $g$. Some well known problems (such as the determinant versus permanent and matrix multiplication for example) are instances of this problem. Given $f$ and $g$ can we determine whether $f$ is an affine projection of $g$?

The intention of this paper is to understand the complexity of the corresponding computational problem: given polynomials $f$ and $g$ find $A$ and $b$ such that $f = g(A x + b)$, if such an $(A, b)$ exists. We first show that this is an NP-hard problem. We then focus our attention on instances where $g$ is a member of some fixed, well known family of polynomials so that the input consists only of the polynomial $f(x)$ having $m$ variables and degree $d$. We consider the situation where $f(x)$ is given to us as a blackbox (i.e. for any point $a \in F^m$ we can query the blackbox and obtain $f(a)$ in one step) and devise randomized algorithms with running time $poly(mnd)$ in the following special cases. Firstly where $g$ is the Permanent (respectively the Determinant) of an $n x n$ matrix and $A$ is of rank $n^2$. Secondly where $g$ is the sum of powers polynomial (respectively the sum of products polynomial), and $A$ is a random matrix of the appropriate dimensions (also $d$ should not be too small).

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable of $g$ by an affine combination of the variables occurring in $f$, then it is said to be an affine projection of $g$. Some well known problems (such as the determinant versus permanent and matrix multiplication for example) are instances of this problem. Given $f$ and $g$ can we determine whether $f$ is an affine projection of $g$?

The intention of this paper is to understand the complexity of the corresponding computational problem: given polynomials $f$ and $g$ find $A$ and $b$ such that $f = g(A x + b)$, if such an $(A, b)$ exists. We first show that this is an NP-hard problem. We then focus our attention on instances where $g$ is a member of some fixed, well known family of polynomials so that the input consists only of the polynomial $f(x)$ having $m$ variables and degree $d$. We consider the situation where $f(x)$ is given to us as a blackbox (i.e. for any point $a \in F^m$ we can query the blackbox and obtain $f(a)$ in one step) and devise randomized algorithms with running time $poly(mnd)$ in the following special cases. Firstly where $g$ is the Permanent (respectively the Determinant) of an $n x n$ matrix and $A$ is of rank $n^2$. Secondly where $g$ is the sum of powers polynomial (respectively the sum of products polynomial), and $A$ is a random matrix of the appropriate dimensions (also $d$ should not be too small).