Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR11-061 | 5th February 2012 14:18

#### Affine projections of polynomials

Revision #1
Authors: Neeraj Kayal
Accepted on: 5th February 2012 14:18
Keywords:

Abstract:

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

### Paper:

TR11-061 | 18th April 2011 15:20

#### Affine projections of polynomials

TR11-061
Authors: Neeraj Kayal
Publication: 18th April 2011 16:51
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).