Revision #2 Authors: Arvind Vikraman, Partha Mukhopadhyay

Accepted on: 22nd April 2008 00:00

Downloads: 3341

Keywords:

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.

Revision #1 Authors: Vikraman Arvind, Partha Mukhopadhyay

Accepted on: 7th December 2007 00:00

Downloads: 2958

Keywords:

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.

TR07-095 Authors: Vikraman Arvind, Partha Mukhopadhyay

Publication: 5th October 2007 13:36

Downloads: 4475

Keywords:

\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.