文章基本信息

标题：Arithmetic Circuit Complexity of Division and Truncation
本地全文：下载
作者：Pranjal Dutta ; Gorav Jindal ; Anurag Pandey 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given polynomials fghF[x1xn] such that f=gh , 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(sdeg(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(sdeg(f)) . Further, we show that any univariate polynomial family (fd)d, defined by the initial segment of the power series expansion of rational function gd(x)hd(x) up to degree d (i.e.~fd=gdhdmodxd+1 ), where circuit size of g is sd and degree of gd is at most d, can be computed by a circuit of size \poly(sddeg(hd)logd) . 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.
关键词：Transcendental power series;Algebraic power series;arithmetic circuits;Division elimination;integer factorization