论文标题
有限阅读公式的总和的限制
Limitations of Sums of Bounded-Read Formulas
论文作者
论文摘要
在代数复杂性理论中，证明各类算术电路计算的超级多项式大小的下限是一项非常重要且具有挑战性的任务。我们将多项式的表示形式研究为较弱的模型的总和，例如读取公式（ROF），并读取曾经删除的代数分支程序（ROABPS）。我们证明： （1）ROF的总和与读取的$ K $公式之间的指数分离。 （2）ROABPS和句法多线性ABP之间的亚指数分离。 我们的结果基于对不同分布下部分导数矩阵的分析。这些结果突出了算术公式和ABP中有限读取限制的丰富性。 最后，我们考虑了[Ramya-Rao，MFCS2019]中定义的被称为严格间隔ABP的多线性ROABP的概括。我们表明，严格的间隔ABP相当于Roabps升至多项式尺寸。相比之下，我们表明间隔公式与ROF不同，并且还承认了深度降低，这在严格间隔ABP的情况下是不知道的。
Proving super polynomial size lower bounds for various classes of arithmetic circuits computing explicit polynomials is a very important and challenging task in algebraic complexity theory. We study representation of polynomials as sums of weaker models such as read once formulas (ROFs) and read once oblivious algebraic branching programs (ROABPs). We prove: (1) An exponential separation between sum of ROFs and read-$k$ formulas for some constant $k$. (2) A sub-exponential separation between sum of ROABPs and syntactic multilinear ABPs. Our results are based on analysis of the partial derivative matrix under different distributions. These results highlight richness of bounded read restrictions in arithmetic formulas and ABPs. Finally, we consider a generalization of multilinear ROABPs known as strict-interval ABPs defined in [Ramya-Rao, MFCS2019]. We show that strict-interval ABPs are equivalent to ROABPs upto a polynomial size blow up. In contrast, we show that interval formulas are different from ROFs and also admit depth reduction which is not known in the case of strict-interval ABPs.
