文章基本信息

标题：Factorization of Polynomials Given by Arithmetic Branching Programs
本地全文：下载
作者：Amit Sinhababu ; Thomas Thierauf
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-20
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s log s ).