Speaker: |
Prerona Chatterjee |

Organiser: |
Vidya Sagar Sharma |

Date: |
Friday, 5 Apr 2019, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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).