Name
Abstract | ||
|---|---|---|
An m-variate polynomial f is said to be an affine projection of some n-variate polynomial g if there exists an nxm matrix A and an n-dimensional vector b such that f (x) = g(Ax + 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. Given f and g can we determine whether f is an affine projection of g ? Some well known problems (such as VP versus VNP and matrix multiplication for example) are instances of this problem. 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(Ax + 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 is an element of 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: (1) when f = Perm(n) (Ax + b) and A satisfies rank(A) = n(2). Here Perm(n) is the permanent polynomial. (2) when f = Det(n)(Ax + b) and A satisfies rank(A) = n(2). Here Det(n) is the determinant polynomial. (3) when f = Pow(n,d)(Ax + b) and A is a random nxm matrix with d = n(Omega(1)). Here Pow(n,d) is the power-symmetric polynomial of degree d. (4) when f = SPSn,d(Ax + b) and A is a random (nd) x m matrix with n constant. Here SPSn,d is the sum-of-products polynomials of degree d with n terms. |
Year | Venue | Keywords |
|---|---|---|
2011 | STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING | Affine Projection,Depth Three Circuit,Determinant,Permanent,Polynomial Equivalence,Reconstruction,Waring Problem for Polynomials |
Field | DocType | Volume |
Affine transformation,Affine involution,Discrete mathematics,Combinatorics,Affine combination,Polynomial,Affine coordinate system,Macdonald polynomials,Affine hull,Geometric complexity theory,Mathematics | Journal | 18 |
Citations | PageRank | References |
2 | 0.35 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |