Revision #1 Authors: Partha Mukhopadhyay

Accepted on: 7th April 2015 05:37

Downloads: 1381

Keywords:

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of

depth-4 circuits. Such circuits compute polynomials of the following type:

$

C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},

$

where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the polynomials

$\{Q_{i,j}\}_{i\in [k], j\in[d_i]}$, and $k,r=O(1)$. We consider a sub-class of such circuits satisfying a \emph{generic} algebraic-geometric restriction, and we give a deterministic polynomial-time black-box identity testing algorithm for such circuits.

Our study is motivated by two recent results of Mulmuley (FOCS 2012), and Gupta (ECCC 2014). In particular, we obtain the derandomization by solving a particular instance of derandomization problem of Noether's Normalization Lemma. Our result can also be considered as a unified way of viewing the depth-4 identity testing problems closely related to the work of

Gupta, and the approach suggested by Mulmuley. The importance of unifying identity testing results is already exhibited by Agrawal et al. via the Jacobian approach (STOC 2012). To the best of our knowledge, the only known result that shows a derandomization of restricted version of Noether's Normalization Lemma in the context of identity testing problem, is the work of Forbes and Shpilka (RANDOM 2013, and FOCS 2013). Forbes and Shpilka considered the black-box identity testing of noncommutative algebraic branching programs (ABPs).

Fixed some minor typos

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of

depth-4 circuits. Such circuits compute polynomials of the following type:

$

C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},

$

where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the polynomials

$\{Q_{i,j}\}_{i\in [k], j\in[d_i]}$, and $k,r=O(1)$. We consider a sub-class of such circuits satisfying a \emph{generic} algebraic-geometric restriction, and we give a deterministic polynomial-time black-box identity testing algorithm for such circuits.

Our study is motivated by two recent results of Mulmuley (FOCS 2012), and Gupta (ECCC 2014). In particular, we obtain the derandomization by solving a particular instance of derandomization problem of Noether's Normalization Lemma. Our result can also be considered as a unified way of viewing the depth-4 identity testing problems closely related to the work of

Gupta, and the approach suggested by Mulmuley. The importance of unifying identity testing results is already exhibited by Agrawal et al. via the Jacobian approach (STOC 2012). To the best of our knowledge, the only known result that shows a derandomization of restricted version of Noether's Normalization Lemma in the context of identity testing problem, is the work of Frobes and Shpilka (RANDOM 2013, and FOCS 2013). Frobes and Shpilka considered the black-box identity testing of noncommutative algebraic branching programs (ABPs).