Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the weighted one.

Let $X=(x_1\ldots x_n), x_i\in \{-1, 1\}$. We define linear weighted threshold element as $f(X)=sgn(\sum_{i=1}^n w_i x_i + w_0)=sgn(F(X)), w_i\in Z$. It has no restrictions on $|w_i|$, and the question is whether $F(X)$ can be represented as linear combination where $|w_i|$ is bounded by polynomial of $n$.

Authors say:

First observe that by considering the binary representation of the weights $w_i$, we can introduce more variables and assign some constant values to renamed variables in such way that any linear threshold function can be assumed to be of the following generic form:

$f(X)=sgn(F(X))$, where $F(X)=\sum_{i=1}^{nlogn} 2^i(x_{1_i}+\ldots +x_{n_i})$

  • I don't get how binary representation of the weights relates to the $logn$ which is defined by $X$ only.
  • Why summation is made for $i=1\ldots nlogn$?
  • It's unclear to me what $x_{k_i}$ stands for.

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.