I need to disprove that a
PARITY gate can be simulated using a single
MAJORITY gate, or even a
THRESHOLD gate. How do I go about doing this? Some ideas as to how to go about contradiction or otherwise would be helpful.
One possible argument would be monotonicity of
PARITY is non-monotone (Page 134 of this paper). But, I do not find this sufficiently convincing.