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 MAJORITY and THRESHOLD while PARITY is non-monotone (Page 134 of this paper). But, I do not find this sufficiently convincing.

  • $\begingroup$ Are you only allowed to use one threshold gate, and nothing else? $\endgroup$ – Yuval Filmus Mar 4 '13 at 15:23
  • $\begingroup$ Since it is a depth one $TC^0$ circuit, we can use only one MAJORITY or THRESHOLD gate and NOT gates. $\endgroup$ – vikraman Mar 4 '13 at 15:44
  • 3
    $\begingroup$ Here's a hint/simplification. Let's suppose you can do that for some $n>2$, then you can fix all inputs except two to zero. Now you have a circuit with two inputs that computes $PARITY(x,y)$. Try to show even this is impossible. $\endgroup$ – sdcvvc Mar 4 '13 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.