Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
share
Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}. An ideal I=〈 p_1(x_1), ..., p_n(x_n)〉 generated by univariate polynomials {p_i(x_i)}_i=1^n is a univariate ideal. We study the ideal membership problem for the univariate ideals and show the following results. * Let f(X)∈F[ℓ_1, ..., ℓ_r] be a (low rank) polynomial given by an arithmetic circuit where ℓ_i : 1≤ i≤ r are linear forms, and I=〈 p_1(x_1), ..., p_n(x_n)〉 be a univariate ideal. Given α⃗∈F^n, the (unique) remainder f(X) I can be evaluated at α⃗ in deterministic time d^O(r)· poly(n), where d={(f),(p_1)...,(p_n)}. This yields an n^O(r) algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields an n^O(r) algorithm for evaluating the permanent of a n× n matrix of rank r, over any field F. Over Q, an algorithm of similar run time for low rank permanent is due to Barvinok[Bar96] via a different technique. * Let f(X)∈F[X] be given by an arithmetic circuit of degree k (k treated as fixed parameter) and I=〈 p_1(x_1), ..., p_n(x_n)〉. We show checking membership of f in I is XP-hard in general. In the special case when I=〈 x_1^e_1, ..., x_n^e_n〉, we obtain a randomized O^*(4.08^k) algorithm that uses poly(n,k) space. * Given f(X)∈F[X] by an arithmetic circuit and I=〈 p_1(x_1), ..., p_k(x_k) 〉, membership testing is W[1]-hard, parameterized by k. The problem is MINI[1]-hard in the special case when I=〈 x_1^e_1, ..., x_k^e_k〉.
READ FULL TEXT