Barriers for Rank Methods in Arithmetic Complexity
Barriers for Rank Methods in Arithmetic Complexity
复制标题
排序方法在算术复杂性方面的障碍
DOI：
10.4230/lipics.itcs.2018.1
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
K. Efremenko;A. Garg;R. Oliveira;A. Wigderson
算术复杂性被认为比布尔复杂性更简单，即通过逻辑门计算布尔函数。确实，与布尔复杂性相比，我们似乎具有更大的下限技术和算术复杂性的结果。尽管取得了许多成功和快速的进步，但是挑战诸如在电路上证明了超级多项式下限或公式大小的显式多项式，或在显式三维张量上的超级线性下限，仍然难以捉摸。
同时，与算术复杂性相比，我们没有证明布尔复杂性的基本下限的“障碍结果”。寻找算术下限技术的障碍似乎更加困难，尽管尝试了一些尝试，但对于这些算术复杂性而言，这些失败的质量没有类似的借口。本文旨在增加这项研究。
我们解决了等级方法，这些方法长期以来被认为涵盖和抽象几乎所有已知的算术下限待办事项，包括最近的令人印象深刻的成功。等级方法（或扁平化）在代数几何形状中也广泛使用，以证明张量等级和对称张量秩下限。我们的主要结果是这些方法的障碍。尤其，
1。等级方法不能比$ \ omega_d（n^{\ lfloor d/2 \ rfloor}）$在任何$ d $ d $二维张量的张张量张量的张张量中的下限。 （特别是，它们无法证明超级线性，甚至对于任何三维张量，甚至$> 8n $张量排列的下限。）
2。等级方法无法证明$ \ omega_d（n^{\ lfloor d/2 \ rfloor}）$在任何$ n $ variate polyenmial for级$ d $的Waring等级上。 （特别是，它们无法证明在更强模型（包括深度-3电路）上的下限。）
Arithmetic complexity is considered simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, challenges like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.
At the same time, we have plenty more "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Finding barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study.
We address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (or flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular,
1. Rank methods cannot prove better than $\Omega_d (n^{\lfloor d/2 \rfloor})$ lower bound on the tensor rank of any $d$-dimensional tensor of side $n$. (In particular, they cannot prove super-linear, indeed even $>8n$ tensor rank lower bounds for any 3-dimensional tensors.)
2. Rank methods cannot prove $\Omega_d (n^{\lfloor d/2 \rfloor})$ on the Waring rank of any $n$-variate polynomial of degree $d$. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.)