Black-box Identity Testing for Low Degree Unmixed \Sigma\Pi\Sigma\Pi(k) Circuits

arXiv1207.5884MaRDI QIDQ6234632FDOQ6234632

Authors: Jinyu Huang 

Publication date: 25 July 2012

Abstract: A $SigmaPiSigmaPi(k)$ circuit $C=su{m}_{i=1}^k{F}_i=su{m}_{i=1}^{k}pro{d}_{j=1}^{d_i}{f}_{ij}$ is unmixed if for each $iin[k]$, $F_i=f_{i1}(x_1)\mathrm{...}{f}_{in}(x_n)$, where each $f_{ij}$ is a univariate polynomial given in the sparse representation. In this paper, we give a polynomial time black-box algorithm of identity testing for the low degree unmixed $SigmaPiSigmaPi(k)$ circuits. In order to obtain the black-box algorithm, we first show that a special class of low degree unmixed $SigmaPiSigmaPi(k)$ circuits of size $s$ is $s^{O(k^2)}$-sparse. Then we construct a hitting set $mathcalH$ in polynomial time for the low degree unmixed $SigmaPiSigmaPi(k)$ circuits from the sparsity result above. The constructed hitting set is polynomial size. Thus we can test whether the circuit or the polynomial $C$ is identically zero by checking whether $C(a)=0$ for each $ainmathcalH$. This is the first polynomial time black-box algorithm for the low degree unmixed $SigmaPiSigmaPi(k)$ circuits, which also partly answers a question of Saxena cite{SAX}.

This page was built for publication: Black-box Identity Testing for Low Degree Unmixed $\Sigma\Pi\Sigma\Pi(k)$ Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234632)