Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR14-130 | 17th October 2014 17:37

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

Revision #1
Authors: Ankit Gupta
Accepted on: 17th October 2014 17:37
Keywords:

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

### Paper:

TR14-130 | 17th October 2014 11:09

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

TR14-130
Authors: Ankit Gupta
Publication: 17th October 2014 17:30
Keywords:

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.

ISSN 1433-8092 | Imprint