pith. sign in

arxiv: 1805.06692 · v2 · pith:EMKIJAY2new · submitted 2018-05-17 · 💻 cs.CC

A Note on Polynomial Identity Testing for Depth-3 Circuits

classification 💻 cs.CC
keywords mathbbpolynomialdepth-3identitytestingalgorithmarithmeticbounded
0
0 comments X
read the original abstract

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

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.