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.
|
Year | DOI | Venue |
---|---|---|
2022 | 10.1007/s00224-021-10053-w | Theory of Computing Systems |
Keywords | DocType | Volume |
Ideal membership, Algorithms, Parameterized complexity, Combinatorial Nullstellensatz | Journal | 66 |
Issue | ISSN | Citations |
1 | 1432-4350 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vikraman Arvind | 1 | 0 | 0.34 |
Abhranil Chatterjee | 2 | 1 | 3.08 |
Rajit Datta | 3 | 1 | 3.75 |
Partha Mukhopadhyay | 4 | 0 | 0.68 |