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 simulable? Circuits of depth 3 or 4, are a good testing ground for this question.
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 will 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). Our de-bordering paradigm has many applications, especially in identity testing and lower bounds.
Based on the works with Prateek Dwivedi & Pranjal Dutta.
This video was produced by the University of Warwick as part of the 7th Workshop on Algebraic Complexity Theory (WACT) 2023.
