Demystifying the border of depth-3 algebraic circuits

Abstract

Border (or approximative) complexity of polynomials plays an integral role in GCT approach to P!=NP. This raises an important open question: can a border circuit be efficiently debordered (i.e. convert from approximative to exact)? Or, could the approximation involve exponential-precision which may not be efficiently simulatable? Circuits of depth 3 or 4, are a good testing ground for this question.

Recently, (Kumar ToCT'20) proved the universal power of the border of top-fanin-2 depth-3 circuits. We recently solved some of the related open questions. In this talk we outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy– it can be computed by a polynomial-size algebraic branching program (ABP). Moreover, we give the first quasipolynomial-time blackbox identity test for the same. Prior best was in PSPACE (Forbes, Shpilka STOC’18). Our de-bordering paradigm builds on the technique what we refer to as DiDIL (divide, derive, induct, with limit).

Based on joint work with Prateek Dwivedi and Nitin Saxena (FOCS 2021; invited to SICOMP). [https://www.cse.iitk.ac.in/users/nitin/papers/border-depth3.pdf]

Video