论文标题
在随机预测下的收缩，以及$ \ mathsf {ac}^0 $的立方公式下限
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
论文作者
论文摘要
$ \ newCommand {\ acz} {\ Mathbf {ac}^0} $Håstad表明，任何de Morgan公式（由和或不是门组成）缩小了$ \ tilde {o} {o}（p^{2}）$在随机的限制下，在每个可变性的情况下，将其与生存的$ po $ po $ po $ prop。使用此结果，他给出了$ \widetildeΩ（n^{3}）$公式大小的尺寸下限为Andreev函数，该功能最多可以进行较低的改进，仍然是任何显式函数的最新下限。 在本文中，我们扩展了Håstad的收缩结果，以在更广泛的随机限制及其概括（随机预测）下。根据我们的收缩结果，我们获得了一个$ \widetildeΩ（n^{3}）$公式大小的下限，用于在$ \ acz $中计算的显式函数。对于$ \ acz $，这仅在我们工作之前仅二次进行了二次，这改善了最著名的公式大小的下限。此外，我们证明了KRW猜想[Karchmer等人，计算复杂性5（3/4），1995]具有内部功能，未加权的量子对手结合紧密。特别是，这适用于具有紧密的Khrapchenko结合的内部功能。 我们的随机预测是针对函数的结构量身定制的，以便该函数即使在投影下也保持结构 - 使用此类预测是必要的，因为标准随机限制简化了$ \ acz $电路。相比之下，我们表明，任何De Morgan公式在我们的随机预测下都会通过二次因素收缩，从而使我们能够证明立方下限。 我们的证明技术建立在Håstad的证明基础上，以简单的平衡配方案例。这允许以稍差的参数为代价实现更简单的证明。因此，当专门针对$ p $ - 随机限制的情况下，我们的证明可以用作Håstad结果的阐述。
$\newcommand{\ACz}{\mathbf{AC}^0}$ Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $\tilde{O}(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\widetildeΩ(n^{3})$ formula size lower bound for the Andreev function, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function. In this paper, we extend the shrinkage result of Håstad to hold under a far wider family of random restrictions and their generalization -- random projections. Based on our shrinkage results, we obtain an $\widetildeΩ(n^{3})$ formula size lower bound for an explicit function computable in $\ACz$. This improves upon the best known formula size lower bounds for $\ACz$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound. Our random projections are tailor-made to the function's structure so that the function maintains structure even under projection -- using such projections is necessary, as standard random restrictions simplify $\ACz$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound. Our proof techniques build on Håstad's proof for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of Håstad's result.
