ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > DEPTH 3 ARITHMETIC CIRCUITS:
Reports tagged with Depth 3 arithmetic circuits:
TR07-095 | 13th July 2007
Vikraman Arvind, Partha Mukhopadhyay

The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2
\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 ... more >>>



ISSN 1433-8092 | Imprint