论文标题
多数的组成复杂性
The composition complexity of majority
论文作者
论文摘要
我们研究计算多数作为本地功能组成的复杂性：\ [\ text {maj} _n = h（g_1，\ ldots，g_m），\ \]，其中$ g_j：\ {0,1 \} \ {0,1 \}^m \ to \ {0,1 \} $是任意组合函数。我们证明了所需的函数数量，证明了\ [m \geΩ\ left（\ frac {n} {k} {k} \ log k \ right）\]的最佳下限，这是一个因子$ω（\ log k）$，大于理想$ m = n/k $。我们将此因素称为开销。以前，其上没有超级恒定的下限以多数闻名。 我们的下边界作为推论，并通过完全不同的证据恢复，这是多数派的有限宽度分支计划的最著名的下限（Alon和Maass '86，Babai等人，Babai等人'90）。这也是我们提出的计划中的第一步，以打破小小的布尔电路的长度障碍。 我们证明的新颖方面包括随着计算流入内部函数$ g_j $流失的信息的尖锐界限，以及用于多出输出功能（锤击权重）的下限的hoottagping降低了单输出一个（多数）的下限。
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each $g_j :\{0,1\}^{n} \to \{0,1\}$ is an arbitrary function that queries only $k \ll n$ variables and $h : \{0,1\}^m \to \{0,1\}$ is an arbitrary combining function. We prove an optimal lower bound of \[ m \ge Ω\left( \frac{n}{k} \log k \right) \] on the number of functions needed, which is a factor $Ω(\log k)$ larger than the ideal $m = n/k$. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority. Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits. Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions $g_j$, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).
