Tata Institute of Fundamental Research
Some Closure Results for Polynomial Factorization and Applications
STCS Seminar
Speaker:
Mrinal Kumar (Simons Institute for the
Theory of Computing
Berkeley, CA 94720-2190)
Organiser:
Ramprasad Saptharishi
Date:
Monday, 7 Jan 2019, 11:00 to 12:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract : In a sequence of seminal results in the 80's, Kaltofen showed that if an n-variate polynomial of degree poly(n) can be computed by an arithmetic circuit of size poly(n), then each of its factors can also be computed an arithmetic circuit of size poly(n). In other words, the complexity class VP (the algebraic analog of P) of polynomials, is closed under taking factors.
A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being fundamental questions on their own, such 'closure results' for polynomial factorization play a crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.
I will talk about the following two results, whose study was motivated by these questions.
1. The class VNP is closed under taking factors.
This proves a conjecture of Bürgisser.
2. All factors of degree at most poly(log n) of polynomials with constant depth circuits of size
poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n).
This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with Chi-Ning Chou and Noam Solomon.
| Speaker: | Mrinal Kumar (Simons Institute for the Theory of Computing Berkeley, CA 94720-2190) |
| Organiser: | Ramprasad Saptharishi |
| Date: | Monday, 7 Jan 2019, 11:00 to 12:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract : In a sequence of seminal results in the 80's, Kaltofen showed that if an n-variate polynomial of degree poly(n) can be computed by an arithmetic circuit of size poly(n), then each of its factors can also be computed an arithmetic circuit of size poly(n). In other words, the complexity class VP (the algebraic analog of P) of polynomials, is closed under taking factors.
A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being fundamental questions on their own, such 'closure results' for polynomial factorization play a crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.
I will talk about the following two results, whose study was motivated by these questions.
1. The class VNP is closed under taking factors.
This proves a conjecture of Bürgisser.
2. All factors of degree at most poly(log n) of polynomials with constant depth circuits of size
poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n).
This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with Chi-Ning Chou and Noam Solomon.
A fundamental question in this line of research, which has largely remained open is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, constant depth arithmetic circuits or the complexity class VNP (the algebraic analog of NP) of polynomials, are closed under taking factors. In addition to being fundamental questions on their own, such 'closure results' for polynomial factorization play a crucial role in the understanding of hardness randomness tradeoffs for algebraic computation.
I will talk about the following two results, whose study was motivated by these questions.
1. The class VNP is closed under taking factors.
This proves a conjecture of Bürgisser.
2. All factors of degree at most poly(log n) of polynomials with constant depth circuits of size
poly(n) have constant (a slightly larger constant) depth arithmetic circuits of size poly(n).
This partially answers a question of Shpilka and Yehudayoff and has applications to hardness-randomness tradeoffs for constant depth arithmetic circuits.
Based on joint work with Chi-Ning Chou and Noam Solomon.