ECCC-Report TR11-061https://eccc.weizmann.ac.il/report/2011/061Comments and Revisions published for TR11-061en-usSun, 05 Feb 2012 14:18:07 +0200
Revision 1
| Affine projections of polynomials |
Neeraj Kayal
https://eccc.weizmann.ac.il/report/2011/061#revision1An $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).
Sun, 05 Feb 2012 14:18:07 +0200https://eccc.weizmann.ac.il/report/2011/061#revision1
Paper TR11-061
| Affine projections of polynomials |
Neeraj Kayal
https://eccc.weizmann.ac.il/report/2011/061An $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).
Mon, 18 Apr 2011 16:51:37 +0300https://eccc.weizmann.ac.il/report/2011/061