Demystifying the border of depth-3 algebraic circuits
Pranjal Kumar Dutta, Prateek Dwivedi, Nitin Saxena · 2022
Border complexity of polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P versus NP. It tries to formalize the notion of ‘approximating a polynomial’ via limits (Bürgisser FOCS'01). This raises the open question whether border of VP is same as VP or not; as the approximation involves exponential precision, which may not be efficiently simulable. Recently (Kumar ToCT'20) proved the universal power of the border of top-fanin-2 depth-3 circuits. Here we answer some of the related open questions. We show that the border of bounded top-fanin-k depth-3 circuits, for constant k, is relatively easy- it can be computed by a polynomial size algebraic branching program (ABP). There were hardly any de-bordering results known for prominent models before our result. Moreover, we give the first quasipolynomial-time black-box identity test for the same. Prior best was in PSPACE (Forbes,Shpilka STOC'18). Also, with more technical work, we extend our results to depth-4. Our de-bordering paradigm is a multi-step process; in short we call it DiDIL -divide, derive, induct, with limit. It ‘almost’ reduces border top-fanin-k depth-3 circuits to special cases of read-once oblivious algebraic branching programs (ROABPs) in any-order. Full version: https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf