论文标题
低深度算术电路通过移动的部分下限
Low-depth arithmetic circuit lower bounds via shifted partials
论文作者
论文摘要
我们使用移动的局部度量[Gupta-kamath-kayal-saptharishi，CCC 2013]，[Kayal，ECCC，2012]和Partials的仿射预测和Partials Measure量度[GARG-KAYAL-SAHA，kayal-saha，kayal-saha，kayal-s-sahaiair stat stats stats state，我们证明了低深度算术电路的超多项式下限。 Limaye，Srinivasan和Tavenas [焦点2021]最近的突破性工作证明了这些下限，这证明了低深度固定 - 式 - 型电路的下限。我们证明的一个有趣的方面是，它不需要将电路转换为设定的单线电路，也不涉及随机限制。我们能够直接限制均质公式的措施，而无需通过固定的义务。我们的下限适用于迭代矩阵乘法以及Nisan-Wigderson设计多项式。我们还定义了一个均匀公式的子类，我们称之为独特的解析树（UPT）公式，并证明这些公式为这些公式。这概括了[Kayal-Saha-Saptharishi，STOC 2014]，[Fournier-limaye-Malod-srinivasan，stoc 2014]中常规公式的超多项式下限。
We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the affine projections of partials measure [Garg-Kayal-Saha, FOCS 2020], [Kayal-Nair-Saha, STACS 2016]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [FOCS 2021] proved these lower bounds by proving lower bounds for low-depth set-multilinear circuits. An interesting aspect of our proof is that it does not require conversion of a circuit to a set-multilinear circuit, nor does it involve a random restriction. We are able to upper bound the measures for homogeneous formulas directly, without going via set-multilinearity. Our lower bounds hold for the iterated matrix multiplication as well as the Nisan-Wigderson design polynomials. We also define a subclass of homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This generalizes the superpolynomial lower bounds for regular formulas in [Kayal-Saha-Saptharishi, STOC 2014], [Fournier-Limaye-Malod-Srinivasan, STOC 2014].
