\(
\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
- $g(\mathbf{0})=0$
- $g(a)=1$ if $a$ contains exactly one $1$
- $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