Tata Institute of Fundamental Research
The class of poly-sized Algebraic Branching Programs is closed under Factoring
STCS Student Seminar
Speaker:
Prerona Chatterjee
Organiser:
Siddharth Bhandari
Date:
Saturday, 18 Jul 2020, 16:00 to 17:00
Venue:
(Scan to add to calendar)
Abstract:
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.
No background of the field will be assumed.
| Speaker: | Prerona Chatterjee |
| Organiser: | Siddharth Bhandari |
| Date: | Saturday, 18 Jul 2020, 16:00 to 17:00 |
| Venue: |
(Scan to add to calendar)
Abstract:
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.
No background of the field will be assumed.
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.
No background of the field will be assumed.