Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?

I do not mean that the input is the infinite set of positive integers. Think of the input as coming on a single wire carrying a non-negative integer.


This is impossible. For large enough $n$, all your threshold gates will be "saturated", that is, they will have the same output on all large enough $n$, and in particular won't be able to distinguish between $n$ and $n+1$.

| cite | improve this answer | |
  • $\begingroup$ Thanks! So the depth 2 representation of PARITY by depth 2 LTF cannot be compressed in any sense. (In terms of size its anyway optimal as was shown in a recent STOC paper that PARITY is $\Theta(\sqrt{n})$ for depth 2 $LTF$) $\endgroup$ – gradstudent Oct 19 '17 at 15:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.