Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties.
Ankit Gupta · Electronic colloquium on computational complexity · 2014
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 P1 · · ·Pd, Q11 · · ·Q1d1 , . . . , Qk1 · · ·Qkdk where k and the degrees of Pi’s and Qij’s are bounded, determines the membership of P1 · · ·Pd in the radical of the ideal generated by Q11 · · ·Q1d1 , . . . , Qk1 · · ·Qkdk in deterministic poly(n, d,maxi(di))-time. We also give a Dvir-Shpilka [DS06]-like approach to resolve the degenerate case and, in the process, initiate a new direction in incidence geometry for non-linear varieties. This approach consists of a series of Sylvester-Gallai type conjectures for boundeddegree 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. ∗Research supported by MSR India PhD Fellowship.