Abstract:
Given a monomial ideal $I={m_1,m_2,...,m_k}$ where $m_i$ are monomials and a polynomial $f$ as an arithmetic circuit the Ideal Membership Problem is to test if $f$ in $I$. We study this problem and show the following results. 1. If the ideal $I={m_1,m_2,....,m_k}$ for a constant $k$ then there is a randomized polynomial-time membership algorithm to test if $f$ is in $I$. This result holds even for $f$ given by a black-box, when $f$ is of small degree. 2. When $I={m_1,m_2,.....m_k}$ for a constant $k$ and $f$ is computed by a $Sigma Pi Sigma$ circuit with output gate of bounded fanin we can test whether $f$ is in $I$ in deterministic polynomial time. This generalizes the Kayal-Saxena result (KS07) of deterministic polynomial-time identity testing for $Sigma Pi Sigma$ circuits with bounded fanin output gate. 3. When $k$ is not constant the problem is coNP-hard. However, the problem is upper bounded by $coAM^{PP}$ over the field of rationals, and by $coNP^{ModpP}$ over finite fields. 4. Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits. For ideals $I={f_1,....,f_l$ where each $f_i$ is in $F[x_1,....,x_k]$ is an arbitrary polynomial but $k$ is a constant, we show similar results as (a) and (b) above.

Abstract:
Given a monomial ideal $I={m_1,m_2,...,m_k}$ where $m_i$ are monomials and a polynomial $f$ as an arithmetic circuit the Ideal Membership Problem is to test if $f$ in $I$. We study this problem and show the following results. 1. If the ideal $I={m_1,m_2,....,m_k}$ for a constant $k$ then there is a randomized polynomial-time membership algorithm to test if $f$ is in $I$. This result holds even for $f$ given by a black-box, when $f$ is of small degree. 2. When $I={m_1,m_2,.....m_k}$ for a constant $k$ and $f$ is computed by a $Sigma Pi Sigma$ circuit with output gate of bounded fanin we can test whether $f$ is in $I$ in deterministic polynomial time. This generalizes the Kayal-Saxena result (KS07) of deterministic polynomial-time identity testing for $Sigma Pi Sigma$ circuits with bounded fanin output gate. 3. When $k$ is not constant the problem is coNP-hard. However, the problem is upper bounded by $coAM^{PP}$ over the field of rationals, and by $coNP^{ModpP}$ over finite fields. 4. Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits. For ideals $I={f_1,....,f_l$ where each $f_i$ is in $F[x_1,....,x_k]$ is an arbitrary polynomial but $k$ is a constant, we show similar results as (a) and (b) above.

Abstract:
\begin{abstract} Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$ are monomials and a polynomial $f$ as an arithmetic circuit the \emph{Ideal Membership Problem } is to test if $f\in I$. We study this problem and show the following results. \begin{itemize} \item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a \emph{constant} $k$ then there is a randomized polynomial-time membership algorithm to test if $f\in I$. This result holds even for $f$ given by a black-box, when $f$ is of small degree.