2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

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

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

Border rank, homogeneity and de-bordering paradigms in GCT

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

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.008
  • Cite this video 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

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback