2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organisateur(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
URL associée https://indico.math.cnrs.fr/event/8113/
8 17

Border rank, homogeneity and de-bordering paradigms in GCT

De Pranjal Dutta

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).

Informations sur la vidéo

Données de citation

  • DOI 10.57987/IHP.2023.T3.WS1.008
  • Citer cette vidéo Dutta, Pranjal (26/09/2023). Border rank, homogeneity and de-bordering paradigms in GCT. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.008
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.008

Domaine(s)

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis