Paper Info
Title
The ideal membership problem and polynomial identity testing
Abstract
Given a monomial ideal I= where m"i are monomials and a polynomial f by an arithmetic circuit, the Ideal Membership Problem is to test if f@?I. We study this problem and show the following results. (a)When the ideal I= for a constant k, we can test whether f@?I in randomized polynomial time. This result holds even for f given by a black-box, when f is of small degree. (b)When I= for a constantkandf is computed by a @S@P@S circuit with output gate of bounded fanin, we can test whether f@?I in deterministic polynomial time. This generalizes the Kayal-Saxena result [11] of deterministic polynomial-time identity testing for @S@P@S circuits with bounded fanin output gate. (c)When k is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMA^P^P over the field of rationals, and by coNP^M^o^d^p^P over finite fields. (d)Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits. For ideals I= where each f"i@?F[x"1,...,x"k] is an arbitrary polynomial but k is a constant, we show similar results as (a) and (b) above.
Year
DOI
Venue
2007
10.1016/j.ic.2009.06.003
Information and Computation
Keywords
Field
DocType
arithmetic circuit,arbitrary polynomial,deterministic polynomial time,randomized polynomial time,bounded fanin,bounded fanin output gate,constant k,Kayal-Saxena result,deterministic polynomial-time identity testing,following result,ideal membership problem,polynomial identity testing
Discrete mathematics,Polynomial identity testing,Combinatorics,Finite field,Rational number,Polynomial,Upper and lower bounds,Monomial ideal,Monomial,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
208
4
Information and Computation
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
V. Arvind112212.03
Partha Mukhopadhyay29112.71