0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Oct 19, 2017 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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