Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-052 | 7th April 2015 05:37

Depth-4 Identity Testing and Noether's Normalization Lemma

RSS-Feed




Revision #1
Authors: Partha Mukhopadhyay
Accepted on: 7th April 2015 05:37
Downloads: 1198
Keywords: 


Abstract:

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



Changes to previous version:

Fixed some minor typos


Paper:

TR15-052 | 6th April 2015 11:54

Depth-4 Identity Testing and Noether's Normalization Lemma





TR15-052
Authors: Partha Mukhopadhyay
Publication: 6th April 2015 15:11
Downloads: 1630
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint