Tata Institute of Fundamental Research
Closure of Small Circuits Under Taking Factors
STCS Student Seminar
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)
Abstract:
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).
| 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)
Abstract:
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).
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).