Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay · Theory of Computing Systems · 2021
Let \({\mathbb {F}}[X]\) be the polynomial ring in the variables X = { x 1 , x 2 ,…, x n } over a field \({\mathbb {F}}\) . 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 . Motivated by Alon’s Combinatorial Nullstellensatz we study the complexity of univariate ideal membership : Given \(f\in {\mathbb {F}}[X]\) by a circuit and polynomials p i the problem is test if f ∈ I . We obtain the following results. Suppose f is a degree- d , rank- r polynomial given by an arithmetic circuit where ℓ i : 1 ≤ i ≤ r are linear forms in X . We give a deterministic time d O ( r ) ⋅poly( n ) division algorithm for evaluating the (unique) remainder polynomial f ( X )mod I at any point \(\vec {a}\in {\mathbb {F}}^{n}\) . This yields a randomized n O ( r ) algorithm for minimum vertex cover in graphs with rank- r adjacency matrices. It also yields a new n O ( r ) algorithm for evaluating the permanent of a n × n matrix of rank r , over any field \(\mathbb {F}\) . Let f be over rationals with \(\deg (f)=k\) treated as fixed parameter. When the ideal \(I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{n}^{e_{n}}}\right \rangle \) , we can test ideal membership in randomized O ∗ ((2 e ) k ). On the other hand, if each p i has all distinct rational roots we can check if f ∈ I in randomized O ∗ ( n k /2 ) time, improving on the brute-force \(\left (\begin {array}{cc}{n+k}\\ k \end {array}\right )\) -time search. If \(I=\left \langle {p_{1}(x_{1}), \ldots , p_{k}(x_{k})}\right \rangle \) , with k as fixed parameter, then ideal membership testing is W[2]-hard. The problem is MINI[1]-hard in the special case when \(I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{k}^{e_{k}}}\right \rangle \) .