Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

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
more >>>


TR18-068 | 8th April 2018
Mrinal Kumar

On top fan-in vs formal degree for depth-3 arithmetic circuits

Revisions: 1

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>


TR18-111 | 4th June 2018
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,
computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or
$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a
deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing
algorithm to check whether $f \equiv 0$ or ... more >>>




ISSN 1433-8092 | Imprint