__
TR18-111 | 4th June 2018 09:19
__

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

**Abstract:**
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 not.

In the case of finite fields, for $\text{Char}(\mathbb{F}) > d$ we obtain a

deterministic algorithm of running time $2^{\gamma\cdot d}\text{poly}(n,s)$,

whereas for $\text{Char}(\mathbb{F})\leq d$, we obtain a deterministic algorithm of

running time $2^{(\gamma+ 2)\cdot d \log d}\text{poly}(n,s)$ where

$\gamma\leq 5$.

__
Comment #1 to TR18-111 | 6th June 2018 14:09
__
#### Relation to earlier works

Authors:

Rajit Datta
Accepted on: 6th June 2018 14:09

Keywords:

**Comment:**
The results over finite fields are subsumed by "Diagonal Circuit Identity Testing and lower bounds" written by Nitin Saxena.

Over characteristics 0 we obtain a substantially faster algorithm running exactly in time $O*(2^d)$ where as Saxena's algorithm runs in time $2^{O(d)}$ (for some constant less than 5).