Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks Yuval! That was slick! :) –  Nikhil Oct 24 '12 at 5:58
    
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$. –  Kristoffer Arnsfelt Hansen Oct 30 '12 at 14:47
    
@Kristoffer You're right, it was a typo. I meant $\geq +1$ and $\leq -1$, as you write. –  Yuval Filmus Oct 30 '12 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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