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

Closure of algebraic complexity classes under factoring by Nitin Saxena

Sep 27, 2023, 11:00 AM
Amphithéâtre Hermite / Darboux (Institut Henri Poincaré)

Amphithéâtre Hermite / Darboux

Institut Henri Poincaré

11 rue Pierre et Marie Curie 75005 Paris


Abstract. 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 VPnb, 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.] []

Presentation materials

There are no materials yet.