Closure Results for Polynomial Factorization
Closure Results for Polynomial Factorization
复制标题
多项式因式分解的收敛结果
作者：
Chi;Mrinal Kumar;Noam Solomon
： Kaltofen （SICOMP 1985, STOC ' 86, STOC ' 87, RANDOM ' 89）在20世纪80年代的一系列基本结果中表明，具有小算术电路的多元多项式的因子具有小算术电路。换句话说，复杂度类VP在取因子下是封闭的。在这种情况下，一个自然的问题是了解其他自然类的多元多项式，例如，算术公式，代数分支程序，有界深度算术电路或类VNP，是否在取因子下是封闭的。在本文中，我们证明了在深度为k的多(n)尺寸回路中，所有的log a n次多项式因子都具有深度为O （k + a）的多(n)尺寸回路。这部分地回答了Shpilka-Yehudayoff的一个问题。TCS趋势，2010)，并应用于有界深度算术电路的硬度-随机性权衡。作为我们技术的直接应用，我们还得到了以下结果的简单证明。
: In a sequence of fundamental results in the 1980s, Kaltofen (SICOMP 1985, STOC’86, STOC’87, RANDOM’89) showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class VP is closed under taking factors. A natural question in this context is to understand if other natural classes of multivariate polynomials, for instance, arithmetic formulas, algebraic branching programs, bounded-depth arithmetic circuits or the class VNP , are closed under taking factors. In this paper, we show that all factors of degree log a n of polynomials with poly ( n ) - size depth-k circuits have poly ( n ) -size circuits of depth O ( k + a ) . This partially answers a question of Shpilka–Yehudayoff (Found. Trends in TCS, 2010) and has applications to hardness–randomness tradeoffs for bounded-depth arithmetic circuits. As direct applications of our techniques, we also obtain simple proofs of the following results.