|
Time: Nov 9, 3:00--4:30 pm. Demystifying the border of depth-3 algebraic circuits Pranjal Dutta Chennai Mathematical Institute (& Visiting Scholar, IIT Kanpur). 09-11-21 Abstract Border complexity of polynomials plays an integral role in GCT (Geometric complexity theory) approach to P != NP. It tries to formalize the notion of ‘approximating a polynomial’ via limits (Burgisser FOCS’01). This raises the open question VP ?= VP; 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 (border-Σ^[2]ΠΣ). Here we answer some of the related open questions. We show that the border of bounded top-fanin depth-3 circuits (border-Σ^[k]ΠΣ 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 blackbox 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-Σ^[k]ΠΣ to special cases of read-once oblivious algebraic branching programs (ROABPs) in any-order.
This is based on a joint work with Prateek Dwivedi (IIT Kanpur) and
Nitin Saxena (IIT Kanpur), which got accepted to FOCS 2021 and invited
to SICOMP Special Issue. A preprint
|
