Tata Institute of Fundamental Research
Arithmetic Circuit Complexity of Division and Truncation
STCS Student Seminar
Speaker:
Gorav Jindal (TU Berlin, Germany.)
Organiser:
Kumar Saurav
Date:
Friday, 11 Jun 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). This result is an exponential improvement over Strassen's classic result (Strassen'73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)).
The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute, unless integer factoring is easy.
This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ .
Zoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
| Speaker: | Gorav Jindal (TU Berlin, Germany.) |
| Organiser: | Kumar Saurav |
| Date: | Friday, 11 Jun 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen'87 & WACT'16). This result is an exponential improvement over Strassen's classic result (Strassen'73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)).
The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute, unless integer factoring is easy.
This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ .
Zoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute, unless integer factoring is easy.
This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ .
Zoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09