We study depth 3 circuits of the form OR AND XOR , or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a 2 ( 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 AC 0 XOR circuits.

For a function f : 0 1 n 0 1 , we denote by DNF ( f ) the least integer s for which there exists an OR AND XOR circuit, with 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 DNF ( f ) 2 n − 2 k . 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 DNF ( f ) 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 DNF ( f ) 1 5 n 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 DNF complexity of 2 n 2 pol y ( n ) . This is also tight up to a polynomial factor.

* For the inner product function IP on n inputs we show that DNF ( IP ) = 2 n 2 − 1 . Previously, Jukna gave a lower bound of ( 2 n 4 ) for the DNF complexity of this function. We further give bounds for any low degree polynomial.