文章基本信息

标题：Factorization of Polynomials Given By Arithmetic Branching Programs
本地全文：下载
作者：Amit Sinhababu ; Thomas Thierauf
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：33:1-33:19
DOI：10.4230/LIPIcs.CCC.2020.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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)).
关键词：Arithmetic Branching Program; Multivariate Polynomial Factorization; Hensel Lifting; Newton Iteration; Hardness vs Randomness