Name
Abstract | ||
|---|---|---|
Given a monomial ideal I = 〈m1, m2,..., mk〉, where mi are monomials, and a polynomial f as an arithmetic circuit the monomial Ideal Membership Problem is to test if f ∈ I. We show that the problem has a randomized polynomial time algorithm for constant k. Furthermore, if k is constant and f is computed by a ΣΠΣ circuit with output gate of bounded fanin then we can test whether f ∈ I in deterministic polynomial time. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77120-3_69 | ISAAC |
Keywords | Field | DocType |
output gate,arithmetic circuit,deterministic polynomial time,monomial ideal,monomial ideal membership problem,randomized polynomial time algorithm,constant k,polynomial identity testing,bounded fanin,polynomial time | Polynomial identity testing,Discrete mathematics,Monomial order,Combinatorics,Minimal polynomial (field theory),Square-free polynomial,Monic polynomial,Monomial basis,Monomial ideal,Monomial,Mathematics | Conference |
Volume | ISSN | ISBN |
4835 | 0302-9743 | 3-540-77118-2 |
Citations | PageRank | References |
17 | 0.78 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |