We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as parity decision trees, the parity kill number and $\mathrm{AC}^{0} \circ \mathrm{XOR}$ circuits.

For a function $f : \{0,1\}^n \to \{0,1\}$, we denote by $\mathrm{DNF}_\oplus(f)$ the least integer $s$ for which there exists an $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$ circuit, with $\mathrm{OR}$ gate of fan-in $s$, that computes $f$. We summarize some of our results:

* For any affine disperser $f$ for dimension $k$, it holds that $\mathrm{DNF}_\oplus(f) \ge 2^{n-2k}$. By plugging Shaltiel's affine disperser (FOCS'11) we obtain an explicit $2^{n-n^{o(1)}}$ lower bound.

* We give a non-trivial general upper bound by showing that $\mathrm{DNF}_\oplus(f) \le O(2^n / n)$ for any function $f$ on $n$ bits. This bound is shown to be tight up to an $O(\log n)$ factor.

* We show that for any symmetric function $f$ it holds that $\mathrm{DNF}_\oplus(f) \le 1.5^n \cdot \mathrm{poly(n)}$. Furthermore, there exists a symmetric function $f$ for which this bound is tight up to a polynomial factor.

* For threshold functions we show tighter bounds. For example, we show that the majority function has $\mathrm{DNF}_\oplus$ complexity of $2^{n/2} \cdot \mathrm{poly}(n)$. This is also tight up to a polynomial factor.

* For the inner product function $\mathrm{IP}$ on $n$ inputs we show that $\mathrm{DNF}_\oplus(\mathrm{IP}) = 2^{n/2}-1$. Previously, Jukna gave a lower bound of $\Omega(2^{n/4})$ for the $\mathrm{DNF}_\oplus$ complexity of this function. We further give bounds for any low degree polynomial.

* Finally, we obtain a $2^{n-o(n)}$ average case lower bound for the parity decision tree model using affine extractors.