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/
11 17

Closure of algebraic complexity classes under factoring

By Nitin Saxena

Polynomial factoring is one of the most fundamental problems in the area of computational algebra. Its variants have attracted a huge amount of attention in the last half-a-century. On the other hand, algebraic complexity theory classifies polynomials, into complexity classes, according to computational resources. Could we show that these classes afford polynomial factoring algorithms? In this talk we will focus on four algebraic complexity classes--- size-s circuits VP_{nb}, size-s degree-s circuits VP, size-s degree-s verifier circuits VNP, and size-s algebraic branching programs VBP. We will discuss the algebraic methods, inspired from analysis, that have been developed to do factoring in these complexity classes. We will list the open questions and make some related conjectures. [This is based on the joint work with Pranjal Dutta, Amit Sinhababu (J.ACM'22, STOC'18), and the follow-up papers by others [https://www.cse.iitk.ac.in/users/nitin/research.html]

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.011
  • Cite this video Saxena, Nitin (27/09/2023). Closure of algebraic complexity classes under factoring. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.011
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.011

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