ECCC-Report TR14-130https://eccc.weizmann.ac.il/report/2014/130Comments and Revisions published for TR14-130en-usFri, 17 Oct 2014 17:37:52 +0300
Revision 1
| Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties |
Ankit Gupta
https://eccc.weizmann.ac.il/report/2014/130#revision1We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we present an algorithm that, given blackboxes to $P_1\cdots P_d$, $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ where $k$ and the degrees of $P_i$'s and $Q_{ij}$'s are bounded, determines the membership of $P_1\cdots P_d$ in the radical of the ideal generated by $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ in deterministic poly($n,d,\max_i(d_i)$)-time.
We also give a Dvir-Shpilka (STOC 2005)-like approach to resolve the degenerate case and, in the process, initiate a new direction in $\textit{incidence geometry for non-linear varieties}$. This approach consists of a series of Sylvester-Gallai type conjectures for bounded-degree varieties and, if true, imply a complete derandomization in the bounded bottom fanin case. To the best of our knowledge, these problems have not been posed before.Fri, 17 Oct 2014 17:37:52 +0300https://eccc.weizmann.ac.il/report/2014/130#revision1
Paper TR14-130
| Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties |
Ankit Gupta
https://eccc.weizmann.ac.il/report/2014/130We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we present an algorithm that, given blackboxes to $P_1\cdots P_d$, $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ where $k$ and the degrees of $P_i$'s and $Q_{ij}$'s are bounded, determines the membership of $P_1\cdots P_d$ in the radical of the ideal generated by $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ in deterministic poly($n,d,\max_i(d_i)$)-time.
We also give a Dvir-Shpilka (STOC 2005)-like approach to resolve the degenerate case and, in the process, initiate a new direction in $\textit{incidence geometry for non-linear varieties}$. This approach consists of a series of Sylvester-Gallai type conjectures for bounded-degree varieties and, if true, imply a complete derandomization in the bounded bottom fanin case. To the best of our knowledge, these problems have not been posed before.Fri, 17 Oct 2014 17:30:49 +0300https://eccc.weizmann.ac.il/report/2014/130