Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Let $\mathbb{F}[X]$ be the polynomial ring over the variables $X={x_1,x_2, \ldots, x_n}$\mathrm{.}Anideal$I=\langle p_1(x_1), \ldots, p_n(x_n)\rangle$generatedbyunivariatepolynomials${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)\in \mathbb{F}[{\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_r]$ be a (low rank) polynomial given by an arithmetic circuit where ${\mathrm{\ell }}_i:1\le i\le r$ are linear forms, and $I=⟨p_1(x_1),\dots ,p_n(x_n)⟩$ be a univariate ideal. Given $\vec{\alpha }\in {\mathbb{F}}^n$, the (unique) remainder $f(X) \pmod I$canbeevaluatedat$\vec{\alpha}$indeterministictime$d^{O®}\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 $n\times 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)\in \mathbb{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$\mathrm{.}Weshowinthespecialcasewhen$I=\langle x_1^{e_1}, \ldots, x_n^{e_n}\rangle$,weobtainarandomized$O^*(4.08^k)$ algorithm that uses $poly(n,k)$ space. \item Given $f(X)\in \mathbb{F}[X]$ by an arithmetic circuit and $I=\langle p_1(x_1), \ldots, p_k(x_k) \rangle$,membershiptestingis$W[1]$-hard, parameterized by $k$. The problem is $MINI[1]$-hard in the special case when $I=⟨x_1^{e_1},\dots ,x_k^{e_k}⟩$.