Closure of Small Circuits Under Taking Factors

Abstract: In the 1980s, Kaltofen proved one of the most remarkable results in algebraic complexity theory. He showed that if a polynomial can be computed by a small circuit, then each of its factors can also be computed by small circuits. In fact, given a circuit for the original polynomial, he also gave an efficient algorithm for computing circuits for the factors. This result has many applications, one of which is the algebraic analogue of the hardness vs randomness question.

In most applications, however, it is only required to show the existence of small circuits for the factors (as opposed to actually computing them). Very recently, Mrinal Kumar, Chi-Ning Chou and Noam Solomon gave a short, simple and almost completely self contained proof of this fact, and in this talk we will discuss their proof. Formally, we will prove the following statement.

If an n variate degree d polynomial f can be computed by an algebraic circuit of size s, then each of its factors can be computed by an algebraic circuit of size at most poly(s, n, d).