8
$\begingroup$

A threshold gate implementing a linear threshold function on $n$ boolean inputs $x_1, x_2 \ldots, x_n$ is given by the equation: $w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$ where $w_1, \ldots, w_n, t \in \mathbb{R}$. The $w_i$'s are called the weights of the threshold function and $t$ is called the threshold, and naturally, the gate fires a $1$ on an input $x$ if the weighted sum given by the equation above exceeds $t$.

Now, almost everywhere in the literature on threshold circuits, I encounter this fact (which I am guessing, is folklore since I couldn't find a proof anywhere): The $w_i$'s in the linear equation above can be made integers (on $n \log{n}$ bits), and a threshold circuit made up of these gates will still compute whatever was possible with real weights. I have given this some thought, and I think it must be a simple trick, but I have failed to obtain a proof of this fact. Can somebody help or provide me with a reference? (the only reference I could find was a text by Muroga, which I couldn't procure)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Given $w_1,\ldots,w_n,t$, let $X$ be the set of assignments such that $\sum_i w_i x_i \geq t$, and consider the linear program with variables $z_1,\ldots,z_n$ and the $2^n$ constraints $$ \begin{align*} \sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\ \sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X \end{align*} $$ This linear program (with a constant objective function) is feasible (since $z_i = w_i/t$ is a solution), and so has a solution $z_1,\ldots,z_n$ which is a vertex. As such, it is the solution of a system of $n$ equations of the form $$ \sum_i z_i x_i = \pm 1. $$ Cramer's rule gives each $z_i$ as a ratio of two $n \times n$ determinants of matrices of $0,\pm 1$ entries; in fact the denominator is the same. Each numerator $N_i$ and the common denominator $D$ is at most $n!$ in magnitude, so multiplying everything by $D$, we get an integral solution $N_1,\ldots,N_n,D$, where all the quantities are at most $n! \leq n^n = 2^{n\log n}$ in magnitude.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ It seems to me that with this linear program you are risking that the vertex solution does not give the same function as the original one: namely, the two sets of equations have the same right-hand side, and hence you risk that the linear form given by the vertex solution have the same value on inputs both from $X$ and not from $X$. To fix this the right-hand sides should be different. The normal proof I know uses $n+1$ variables (that is, also a variable for $t$) and uses the right-hand sides $-1$ and $1$. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Oct 30, 2012 at 14:47
  • $\begingroup$ @Kristoffer You're right, it was a typo. I meant $\geq +1$ and $\leq -1$, as you write. $\endgroup$
    – Yuval Filmus
    Oct 30, 2012 at 14:56
  • $\begingroup$ @YuvalFilmus Is there a typo in how you are counting the number of equations to solve? It seems like you have $2^n$ simultaneous linear equations to solve. (one for each $x$) And hence all solutions are at most $(2^n)!$ in magnitude because the Cramer's rule matrices are $2^n$ dimensional. Am I missing something? $\endgroup$
    – gradstudent
    Oct 30, 2017 at 23:13
  • $\begingroup$ Oh! Wait! Are you saying that one can choose any $n$ of the $x$s arbitarily and solving for this subsystem is enough to give you a vertex and hence you are done? $\endgroup$
    – gradstudent
    Oct 30, 2017 at 23:16
  • $\begingroup$ A vertex is the solution of $n$ linearly independent equations. $\endgroup$
    – Yuval Filmus
    Oct 31, 2017 at 13:12

Your Answer

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

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