We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega \left( n^{1/\Delta}/\Delta\right)}$. The hard polynomial $f$ comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form $(\log n)^{\Omega (\Delta n^{1/\Delta})}$ was shown for the size of product-depth $\Delta$ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as $f$. Moreover, our lower bounds are novel for any $\Delta\geq 2$. For general set-multilinear formulas, a lower bound of the form $ n^{\Omega(\log n)}$ was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form $(\log n)^{\Omega(\log n)}$ for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form $n^{\Omega(\log n)}$, albeit for the same polynomial $f$ in VNP (the NW polynomial). As observed by LST, if the same $n^{\Omega(\log n)}$ size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.
翻译:更确切地说,我们显示,在任何字段中,在以美元为单位的 VNP 中有一个明确的多面价美元,定义的值是美元2美元变量,度值是美元,因此,任何以美元为单位的设定-多线公式计算美元,其大小至少为$@ ⁇ 1/\Delta}左(n ⁇ 1/\Delta}/\Delta\right)美元。在任何字段中,硬的多面价美元来自以美元为单位的 Nsan-Wigderson (NW) 设计以美元为单位的多面值公式。在利马耶、斯里尼瓦桑和塔韦纳斯(STOC 2022)最近的工作中,我们的下面值美元(美元=Omega) 固定值至少为美元(\\\\\\\\\\\\Delta}}}以美元为单位。 以美元为单位的更下面值的基面值公式,如果以美元为单位的基数(IMM),则以美元为单位的多面值的基的基数表示。