Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-111 | 4th June 2018 09:19

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

TR18-111
Authors: Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay
Publication: 4th June 2018 22:16
Keywords:

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(s):

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).

ISSN 1433-8092 | Imprint