Advertisement
Published in:
15-07-2021
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
Published in: Theory of Computing Systems | Issue 1/2022
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \({\mathbb {F}}[X]\) be the polynomial ring in the variables X = {x1,x2,…,xn} over a field \({\mathbb {F}}\). An ideal I = 〈p1(x1),…,pn(xn)〉 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 pi 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 dO(r) ⋅poly(n) division algorithm for evaluating the (unique) remainder polynomial f(X)modI at any point \(\vec {a}\in {\mathbb {F}}^{n}\). This yields a randomized nO(r) algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields a new nO(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∗((2e)k). On the other hand, if each pi has all distinct rational roots we can check if f ∈ I in randomized O∗(nk/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 \).