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

• Published in: arXiv.org 2018-09
• Main Authors: Arvind, V, Chatterjee, Abhranil, Datta, Rajit, Mukhopadhyay, Partha
• Format: Article
• Language: English
• Subjects: Algorithms; Arithmetic; Circuits; Mathematical analysis; Parameterization; Polynomials; Rings (mathematics); Run time (computers)
• ISSN: 2331-8422

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)\in\mathbb{F}[\ell_1, \ldots, \ell_r]\) be a (low rank) polynomial given by an arithmetic circuit where \(\ell_i : 1\leq i\leq 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 \(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\). 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)\in\mathbb{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\).