ECCC-Report TR07-095https://eccc.weizmann.ac.il/report/2007/095Comments and Revisions published for TR07-095en-usTue, 22 Apr 2008 00:00:00 +0300
Revision 2
| The Ideal Membership Problem and Polynomial Identity Testing |
Arvind Vikraman,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2007/095#revision2 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.
Tue, 22 Apr 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/095#revision2
Revision 1
| The Ideal Membership Problem and Polynomial Identity Testing |
Vikraman Arvind,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2007/095#revision1Given 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.
Fri, 07 Dec 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/095#revision1
Paper TR07-095
| The Ideal Membership Problem and Polynomial Identity Testing |
Vikraman Arvind,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2007/095\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.
Fri, 05 Oct 2007 13:36:03 +0200https://eccc.weizmann.ac.il/report/2007/095