Loading jsMath...
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: 3769
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: 3373
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: 4775
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