论文标题
新的指数尺寸下限与深度四个界单个学位的四个电路
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree
论文作者
论文摘要
Kayal，Saha和Tavenas [计算理论，2018年]表明，对于所有足够大的整数$ n $和$ d $ $ n^{ω\ left（\ sqrt {d/δ} \ right）} $。不幸的是，随着$δ$的值增加，这种结合会恶化。此外，仅当$δ$为$ o（d）$时，该界限才是超级单位。自然要问是否可以削弱对$δ$的依赖。为此，在较早的结果[Stacs，2020年]中，我们表明，对于所有足够大的整数$ n $和$ d $，使得$ d =θ（\ log^2 {n}）$，任何语法深度四个有限的个体度$δ\Δ\ leq n^{0.2} $ size $ ums $ gle yq $ ums_ n，d y，d y，D $ n^{ω（\ log {n}）} $。 在本文中，我们通过证明所有足够大的整数$ n $ and $ d $以及绝对常数$ a $ a $ a and $ b $的进一步取得进展$ n^{ω（\ sqrt {d}）} $。通过仔细调整Kumar和Saraf的证明[Siam J. Computing，2017]来获得我们的界限，以在我们早期的工作[Stacs，2020]中引入的复杂性度量。
Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq ω(\log{n})$, any syntactic depth four circuit of bounded individual degree $δ= o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{Ω\left(\sqrt{d/δ}\right)}$. Unfortunately, this bound deteriorates as the value of $δ$ increases. Further, the bound is superpolynomial only when $δ$ is $o(d)$. It is natural to ask if the dependence on $δ$ in the bound could be weakened. Towards this, in an earlier result [STACS, 2020], we showed that for all large enough integers $n$ and $d$ such that $d = Θ(\log^2{n})$, any syntactic depth four circuit of bounded individual degree $δ\leq n^{0.2}$ that computes $IMM_{n,d}$ must have size $n^{Ω(\log{n})}$. In this paper, we make further progress by proving that for all large enough integers $n$ and $d$, and absolute constants $a$ and $b$ such that $ω(\log^2n)\leq d\leq n^{a}$, any syntactic depth four circuit of bounded individual degree $δ\leq n^{b}$ that computes $IMM_{n,d}$ must have size $n^{Ω(\sqrt{d})}$. Our bound is obtained by carefully adapting the proof of Kumar and Saraf [SIAM J. Computing, 2017] to the complexity measure introduced in our earlier work [STACS, 2020].
