ECCC-Report TR15-052https://eccc.weizmann.ac.il/report/2015/052Comments and Revisions published for TR15-052en-usTue, 07 Apr 2015 05:37:07 +0300
Revision 1
| Depth-4 Identity Testing and Noether's Normalization Lemma |
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2015/052#revision1We 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).
Tue, 07 Apr 2015 05:37:07 +0300https://eccc.weizmann.ac.il/report/2015/052#revision1
Paper TR15-052
| Depth-4 Identity Testing and Noether's Normalization Lemma |
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2015/052We 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).
Mon, 06 Apr 2015 15:11:22 +0300https://eccc.weizmann.ac.il/report/2015/052