In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR.

I tried for a little bit to figure out how to do this, but couldn't find such a construction. How do you do this?

  • $\begingroup$ The claim assumes that you can use both the inputs and the negations of the inputs. Does that help? $\endgroup$ – Wandering Logic Mar 12 '19 at 21:24
  • $\begingroup$ Nice question! It's easy to see how to do it in depth 4, and that suffices for the point made in those notes (deeper circuits can help). I still don't see how to do it in depth 3, though. $\endgroup$ – D.W. Mar 12 '19 at 21:38
  • $\begingroup$ Compose two XORs on $\sqrt n$ bits. Use both a CNF and a DNF for the lower XORs (and use de Morgan liberally). $\endgroup$ – Yuval Filmus Mar 12 '19 at 23:05
  • $\begingroup$ I think basically the idea is that you can use the CNF on the top and the DNF on the bottom. You can collapse the ANDs by associativity. Yes, you have negations in the middle but by de Morgan's law you can push them down. $\endgroup$ – Josh B. Mar 13 '19 at 3:08

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.