Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-111 | 4th June 2018 09:19

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

RSS-Feed

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