Lesson 6

The function \([x_{1}=a_{1}, \dotsc, x_{r}=a_{r}] \in B_{r}\) is a function of \(r\) variables that is equal to one at exactly one point. It is also called a (literal) monomial because it is simply the product of literals: for example, \([x_{1}=0, x_{2}=1, x_{3}=0]=\overline{x_1}x_{2}\overline{x_3}\) (the omitted binary operations, as usual, represent binary products, i.e., \(\land\)).

Lemma. The functions \([x_{1}=a_{1}, \dotsc, x_{r}=a_{r}]\) for all \(a \in \{0,1\}^{r}\) can be computed simultaneously by a circuit of size \(O(2^{r})\).

Proof. If we compute each such function separately, we get a circuit of size \(r \cdot 2^{r}\). We will proceed more cleverly: divide the variables into two parts and compute all such monomials over the first half and all such monomials over the second half naively; after that, any monomial over \(r\) variables will be obtained as the product of two small monomials. In total, we will use \[2 \cdot \frac{r}{2}\cdot 2^{\frac{r}{2}}+ 2^{r}=O(2^{r})\] gates.◼