__
Revision #1 to TR14-130 | 17th October 2014 17:37
__
#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

**Abstract:**
We 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.

**Changes to previous version:**
fixed some typos

__
TR14-130 | 17th October 2014 11:09
__

#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

**Abstract:**
We 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.