The Complexity of DNF of Parities
Gil Cohen, Igor Shinkar · 2016
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, using graph theoretic arguments, for explicit functions. Several related models have gained attention in the last few years, such as parity decision trees, the parity kill number and AC0-XOR circuits.