Let $mathbb{F}[X]$ be the polynomial ring over the variables $X={x_1,x_2, ldots, x_n}$. An ideal $I=langle p_1(x_1), ldots, p_n(x_n)rangle$ generated by univariate polynomials ${p_i(x_i)}_{i=1}^n$ is a emph{univariate ideal}. We study the ideal membership problem for the univariate ideals and show the following results. item Let $f(X)inmathbb{F}[ell_1, ldots, ell_r]$ be a (low rank) polynomial given by an arithmetic circuit where $ell_i : 1leq ileq r$ are linear forms, and $I=langle p_1(x_1), ldots, p_n(x_n)rangle$ be a univariate ideal. Given $vec{alpha}in {mathbb{F}}^n$, the (unique) remainder $f(X) pmod I$ can be evaluated at $vec{alpha}$ in deterministic time $d^{O(r)}cdot poly(n)$, where $d=max{deg(f),deg(p_1)ldots,deg(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 $ntimes n$ matrix of rank $r$, over any field $mathbb{F}$. Over $mathbb{Q}$, an algorithm of similar run time for low rank permanent is due to Barvinok[Bar96] via a different technique. item Let $f(X)inmathbb{F}[X]$ be given by an arithmetic circuit of degree $k$ ($k$ treated as fixed parameter) and $I=langle p_1(x_1), ldots, p_n(x_n)rangle$. We show in the special case when $I=langle x_1^{e_1}, ldots, x_n^{e_n}rangle$, we obtain a randomized $O^*(4.08^k)$ algorithm that uses $poly(n,k)$ space. item Given $f(X)inmathbb{F}[X]$ by an arithmetic circuit and $I=langle p_1(x_1), ldots, p_k(x_k) rangle$, membership testing is $W[1]$-hard, parameterized by $k$. The problem is $MINI[1]$-hard in the special case when $I=langle x_1^{e_1}, ldots, x_k^{e_k}rangle$.
Download