论文标题
代数分支程序和分层的下限
Lower Bounds of Algebraic Branching Programs and Layerization
论文作者
论文摘要
在本文中，我们将Chatterjee等人的下限（ECCC 2019）提高到$ω（n^2）$下限$下限，用于不合理的代数分支程序。我们也是 研究对代数分支程序的影响分层对代数分支程序的影响。我们展示了一个多项式，其尺寸为$ o（n）$，但任何分层ABP的大小至少$ω（n \ sqrt {n}）$。 我们在非共同环境中表现出类似的二分法，其中未释放的ABP具有$ o（n）$，并且任何分层ABP的大小至少$ω（n \ log n -log n- \ log^2 n）$。
In this paper we improve the lower bound of Chatterjee et al.\ (ECCC 2019) to an $Ω(n^2)$ lower bound for unlayered Algebraic Branching Programs. We also study the impact layerization has on Algebraic Branching Programs. We exhibit a polynomial that has an unlayered ABP of size $O(n)$ but any layered ABP has size at least $Ω(n\sqrt{n})$. We exhibit a similar dichotomy in the non-commutative setting where the unlayered ABP has size $O(n)$ and any layered ABP has size at least $Ω(n\log n -\log^2 n)$.
