In this section we prove that the parity function has exponentially small correlation with small bounded-depth circuits. To formally state the result, let us make its main players more concrete. First, the parity function Parity : {0,1}~n→ {0,1} is the degree-1 polynomial over {0,1} defined as:rnParity_n(x_1,x_2,...,x_n) := Σ_i x_i mod 2.rnSecond, the circuits we consider consist of input, A (and), V (or), and (not) gates, where the input gates are labeled with variables (e.g., x_i), and A and V gates have unbounded fan-in. The size w of the circuit is the number of edges, and its depth d is the longest path from an input gate to the output gate. With a moderate blow-up, it is possible to "push down" all the gates so that the circuit takes as input both the variables and their negations, but consists only of alternating layers of A and V gates, hence the name alternating circuit (AC~0). We do so in Section 4, but in this one we find it more convenient to allow for gates everywhere in the circuit.
展开▼
机译：在本节中，我们证明奇偶校验函数与较小的深度边界电路具有指数相关的较小关系。为了正式陈述结果，让我们使其主要参与者更加具体。首先，奇偶校验函数Parity：{0,1}〜n→{0,1}是{0,1}上的1阶多项式，定义为：rnParity_n（x_1，x_2，...，x_n）：=Σ_i x_i mod 2.rn其次，我们考虑的电路包括输入，A（和），V（或）和（非）门，其中输入门标有变量（例如x_i），A和V门具有无限制的扇入。电路的大小w是边的数量，其深度d是从输入栅极到输出栅极的最长路径。通过适度的爆破，可以“下推”所有门，以使电路以变量和它们的取反作为输入，但仅由A和V门的交替层组成，因此名称为Alternate circuit（ AC〜0）。我们在第4节中这样做了，但是在这一节中，我们发现在电路中的任何地方都可以设置门更为方便。
展开▼
