\( \def\<#1>{\left<#1\right>} \newcommand{\CC}{\mathbf{C}} \newcommand{\F}{\mathcal{F}} \newcommand{\disjpairs}{\mathcal{D}} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

A correction to Remark 11.28

We formulated Thm. 11.25 only for $\Sigma_3^{\oplus}$ circuits. Each of them is an OR of ANDs of parities or their negations. The difference from standard $\Sigma_3$ circuits is that now we have Parities instead of ORs on the bottom (next to the inputs) level. However, the proof of Thm. 11.25 gives the same lower bound also for depth-$3$ circuits, where at the bottom level, any "isolating" functions are allowed. A boolean function $g:\{0,1\}^n\to\{0,1\}$ is isolating if
  1. $g(\mathbf{0})=0$
  2. $g(a)=1$ if $a$ contains exactly one $1$
  3. $g(a)=0$ if $a$ contains exactly two $1$s

For example, for every integer $p\geq 2$, the boolean function MOD$_p(x)$, which outputs $1$ iff $\sum_{i=1}^n x_i \pmod{p} =1$, is isolating.

Properties (1) and (2) are needed for the Magnification Lemma (Lemma 1.32, going from boolean functions to graphs) to hold. Property (3) is needed in the proof of Lemma 11.26 (for the gate $g$ to correspond to a fat matching). In Remark 11.28, this last condition (3) is (wrongly) missing. Note that the OR function satisfies (1) and (2), but not (3), so that that the proof of Thm. 11.25 does not work for usual $\Sigma_3$ circuits.

S. Jukna, March 4, 2015