Polynomial factorization is one of the fundamental questions in algebraic complexity. Given a multivariate polynomial f in the form of a succinct representation (e.g., arithmetic circuit), the task is finding a succinct representation for its factors. In addition to being a natural question, polynomial factorization has many applications such as hardness versus randomness and decoding Reed-Solomon codes.
An arithmetic circuit class C is closed under factor if the following holds: let f be a polynomial in class C, then its factors also lie in C. In this talk, I’m going to focus on two recent closure results in polynomial factorization. The first one is for constant depth arithmetic circuits of poly-logarithmic degree and the second one is for VNP. Some applications of these results and future direction will also be discussed.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
