论文标题
关于Read-Once遗忘ABP的子类之间的分离
On Finer Separations between Subclasses of Read-once Oblivious ABPs
论文作者
论文摘要
读取对遗漏的代数分支程序（ROABP）将多项式计算为具有矩阵作为系数的单变量多项式的产物。为了了解ROABP的代数复杂性类别的景观，我们根据这些系数矩阵的代数结构来研究ROABPS类。我们研究由ROABP的这些结构化变体计算的多项式与其他众所周知的多项式类别（例如深度三个动力电路，张量和多项式级别级别）。 我们的主要结果是涉及到可接班人的ROABP，所有系数矩阵彼此通勤，对角ROABP，所有系数矩阵都只是对角线矩阵。特别是，我们在这些模型与与多项式的战争级别相关的深度 - 三个动力电路模型之间显示了一个令人惊讶的联系。我们表明，如果部分衍生物的维度捕获了多项式因素的捕获，那么对角ROABPS的模型有效地模拟了看似更具表现力的Roabps模型。此外，无法通过对角线ROABP有效模拟的交换性ROABP将提供一个显式多项式，从而在部分衍生物的维度和沃克级之间给出超多项式分离。 我们对上述结果的证明是建立在Marinari，Möller和Mora（1993）和Möllerand Stetter（1995）的基础上，这些结果表征了通勤矩阵的环，其矩阵的矩阵的多项式具有部分衍生物的尺寸。这些ROABP的系数矩阵的代数结构在我们的证明中起着至关重要的作用。
Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials). Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank. Our proof of the above result builds on the results of Marinari, Möller and Mora (1993), and Möller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs.
