Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-095 | 22nd April 2008 00:00

The Ideal Membership Problem and Polynomial Identity Testing

RSS-Feed




Revision #2
Authors: Arvind Vikraman, Partha Mukhopadhyay
Accepted on: 22nd April 2008 00:00
Downloads: 1395
Keywords: 


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.


Revision #1 to TR07-095 | 7th December 2007 00:00

The Ideal Membership Problem and Polynomial Identity Testing





Revision #1
Authors: Vikraman Arvind, Partha Mukhopadhyay
Accepted on: 7th December 2007 00:00
Downloads: 1182
Keywords: 


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.


Paper:

TR07-095 | 13th July 2007 00:00

The Ideal Membership Problem and Polynomial Identity Testing





TR07-095
Authors: Vikraman Arvind, Partha Mukhopadhyay
Publication: 5th October 2007 13:36
Downloads: 2272
Keywords: 


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.



ISSN 1433-8092 | Imprint