License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.25
URN: urn:nbn:de:0030-drops-142990
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14299/
Dutta, Pranjal ;
Jindal, Gorav ;
Pandey, Anurag ;
Sinhababu, Amit
Arithmetic Circuit Complexity of Division and Truncation
Abstract
Given polynomials f,g,h ∈ ?[x₁,…,x_n] 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). The 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)).
Further, we show that any univariate polynomial family (f_d)_d, defined by the initial segment of the power series expansion of rational function g_d(x)/h_d(x) up to degree d (i.e. f_d = g_d/h_d od x^{d+1}), where circuit size of g is s_d and degree of g_d is at most d, can be computed by a circuit of size poly(s_d,deg(h_d),log d). We also show a hardness result when the degrees of the rational functions are high (i.e. Ω (d)), assuming hardness of the integer factorization problem.
Finally, we extend this conditional hardness to simple algebraic functions as well, and show that for every prime p, there is an integral algebraic power series with its minimal polynomial satisfying a degree p polynomial equation, such that its initial segment is hard to compute unless integer factoring is easy, or a multiple of n! is easy to compute. Both, integer factoring and computation of multiple of n!, are believed to be notoriously hard. In contrast, we show examples of transcendental power series whose initial segments are easy to compute.
BibTeX - Entry
@InProceedings{dutta_et_al:LIPIcs.CCC.2021.25,
author = {Dutta, Pranjal and Jindal, Gorav and Pandey, Anurag and Sinhababu, Amit},
title = {{Arithmetic Circuit Complexity of Division and Truncation}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {25:1--25:36},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14299},
URN = {urn:nbn:de:0030-drops-142990},
doi = {10.4230/LIPIcs.CCC.2021.25},
annote = {Keywords: Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization}
}
|
Keywords: |
|
Arithmetic Circuits, Division, Truncation, Division elimination, Rational function, Algebraic power series, Transcendental power series, Integer factorization |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
