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 TR14-130 | 17th October 2014 17:37

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

RSS-Feed




Revision #1
Authors: Ankit Gupta
Accepted on: 17th October 2014 17:37
Downloads: 862
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
Downloads: 562
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