Sep 18 – 29, 2023
Institut Henri Poincaré
Europe/Paris timezone

Border rank, homogeneity and de-bordering paradigms in GCT by Pranjal Dutta

Sep 26, 2023, 2:00 PM
Amphithéâtre Hermite / Darboux (Institut Henri Poincaré)

Amphithéâtre Hermite / Darboux

Institut Henri Poincaré

11 rue Pierre et Marie Curie 75005 Paris


Abstract. Border (or approximative) complexity of polynomials plays an integral role in GCT (Geometric Complexity Theory) approach to P!=NP. This raises an important basic question: can arbitrary approximations of simple polynomials involve exponential-precision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question. Recently, Kumar proved that any polynomial f can be approximated arbitrarily well by restrictions of the polynomial x1 ... xn - 1 for n large enough. In this talk, we will see a stronger connection (& reverse) of this result with the border rank of f, and how homogeneity can play an important role in border complexity.
Furthermore, we will see the border of constant top-fanin depth-3 circuits (which is far more general than x1...xn -1) is relatively easy & hierarchical - it can be computed by a polynomial-size algebraic branching program (ABP).
This is based on the joint works with -- 1) Prateek Dwivedi & Nitin Saxena (FOCS'21) 2) Nitin Saxena (FOCS'22) 3) Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal and Vladimir Lysikov (submitted).

Presentation materials

There are no materials yet.