Talk will be held in Zoom.
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.
However, his proof did not extend to more restricted models of computation. Recently Amit Sinhababu and Thomas Thierauf showed a similar statement for the class of Algebraic Branching Programs (or ABPs). Formally, they proved the following statement. If an n variate degree d polynomial f can be computed by an ABP of size s, then each of its factors can be computed by an ABP of size at most poly(s, n, d).
In this talk, we will go over the proof techniques used in the previous results of this kind, and see an overview of the modifications Sinhababu and Theirauf made to these techniques to get their result.
