Let me split my query into a few parts which possibly have overlapping answers,

  1. How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) are in $NP/poly$? (I saw this claimed in the conclusion of this recent paper https://arxiv.org/abs/1705.02397 without any proof or reference.)

  2. Why is depth $3$ special here? What is the analogous statement for higher depths? Are they outside $NP/poly$?

  3. Apparently it is also true that all of polynomial sized threshold circuits are in $P/poly$. How do we prove this?

  4. Isn't $P/poly \subseteq NP/poly$? And in that case why would anyone want to emphasize that $\hat{LT_3} \subseteq NP/poly$ when we know that $\hat{LT_3} \subseteq P/poly$? What am I missing?

  • $\begingroup$ A good start would be to provide some references. I suspect that you are skipping some subtleties. $\endgroup$ – Yuval Filmus Oct 7 '17 at 10:23
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Oct 7 '17 at 10:29
  • 1
    $\begingroup$ Also, please ask only one question per post. It seems to me those four are independent enough to be asked and answered in sequence, but answering one may change or obsolete later ones. $\endgroup$ – Raphael Oct 7 '17 at 10:29
  • $\begingroup$ @YuvalFilmus I have added a reference for the first point. The rest are not specific to any reference. It would be very helpful if you could share your thoughts on these issues. $\endgroup$ – gradstudent Oct 7 '17 at 16:12
  • $\begingroup$ @Raphael Because answering one can change or obsolete the other questions I put them together and not in separate questions. I think it would be very messy to split them when they are I think very tied into each other. $\endgroup$ – gradstudent Oct 7 '17 at 16:14

First, let me correct you definition of $\widehat{LT}\!\!_3$: it is the class of depth-3 polynomial size threshold circuits with polynomially bounded weights.

Polynomial size threshold circuits can be converted to polynomial size Boolean circuits. To show this, it suffices to show that any single threshold gate can be computed by a polynomial size Boolean circuit. The proof goes along the following lines:

  • Every threshold gate is equivalent to a threshold gates whose weights have bit-length $O(m\log m)$, where $m$ is the number of inputs. This can be shown using linear programming (see below).
  • Adding $m$ numbers of bit-length $O(m\log m)$ can be accomplished using a Boolean circuit of size polynomial in $m$.

In our case $m$ is at most the number of gates in the original threshold circuit, which is polynomial (in $n$, the number of input bits). Therefore the Boolean circuit equivalent to any single threshold gate has polynomial size.

The foregoing shows that $\widehat{LT}\!\!_3 \subseteq \mathrm{P/poly}$. While it is also true that $\widehat{LT}\!\!_3 \subseteq \mathrm{NP/poly}$, it seems like a typo in the paper.

Finally, let us indicate how to show that every threshold gate on $m$ inputs is equivalent to one in which the weights have bit-length $O(m\log m)$. Consider the following linear program. The variables are $c_1,\ldots,c_m,\theta$. For each $x_1,\ldots,x_m \in \{0,1\}^m$, if the threshold gate outputs 1 on this input, we add the constraint $$ \sum_{i=1}^m c_i x_i \geq \theta + 1, $$ and if it outputs 0 then we add the constraint $$ \sum_{i=1}^m c_i x_i \leq \theta - 1. $$ It is not too hard to check that this LP is feasible, essentially using the parameters of the threshold gate (possibly scaled). On the other hand, LP theory tells us that there exists a basic feasible solution, which is obtained by choosing $m+1$ linearly independent inequalities and treating them as equations. Cramer's rule, which expresses the solution as a ratio of determinants, completes the proof (exercise).

| cite | improve this answer | |
  • $\begingroup$ Thanks for the reply! Let me read this carefully and get back to you! $\endgroup$ – gradstudent Oct 9 '17 at 16:06

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.