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, lower bounds, and factorization.
Based on the works with Prateek Dwivedi & Pranjal Dutta (CCC 2021) + (FOCS 2021, invited to SICOMP) + (FOCS 2022) + (STOC 2024). [https://www.cse.iitk.ac.in/users/nitin/research.html]
Short Bio:
Nitin pursued his education at IIT Kanpur and completed his PhD there. He undertook research stints at Princeton University and the National University of Singapore before joining CWI Amsterdam and later the University of Bonn. Currently, he holds a professorship at IIT Kanpur and serves as the N.Rama.Rao Chair, alongside adjunct faculty roles elsewhere. Notably, he spearheads the "Center for Developing Intelligent Systems" to tackle governance challenges at scale. In the realm of algebraic complexity, Nitin has made significant strides, addressing prominent open problems through co-authored papers and pioneering algorithmic-algebraic techniques. Active within the academic community, Nitin engages in various committees and policy-making endeavors. Recognized for his contributions, he has received numerous accolades, including the Gödel Prize, Fulkerson Prize, and Shanti Swarup Bhatnagar Prize.
