<p>If I understand your question correctly the answer is yes. In the paper</p>

<p>"Majority Gates Vs. General Weighted Threshold Gates" (http://www.nada.kth.se/~johanh/majorityvsthreshold.pdf) by Goldman, Håstad, and Razborov</p>

<p>They show that anything that can be computed by a depth $d$ threshold circuit can be computed by a depth $d+1$ unweighted threshold circuit of poly size.</p>

<p>Your question seems to be a special case of this for $d=1$.</p>

CC BY-SA 3.0
2013-01-18T08:45:36.223Z
2013-01-18T08:45:36.223Z
Magnus Find
<p>I have a question about a answer of a question which is proposed in this stack exchange.</p>

<h1>The Past Question</h1>

<p>One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma. </p>

<p>Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.</p>

<p>My question is about upper bound of Threshold function which is a natural generalization of majority function. </p>

<p>The formal definition of the threshold function is the following one. </p>

<p>DEFINITION:</p>

<p>$THR(x_{1},...,x_{n})=
  \begin{cases}
    1 &amp; a_{1}x_{1}+\cdots +a_{n}x_{n} \geq t \\
    0 &amp; otherwise
  \end{cases}
$</p>

<p>We assume that each weight $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$</p>

<p>QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?</p>

<p>Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .</p>

<h1>Answer</h1>

<p>Kristoffer Arnsfelt Hansen said that:</p>

<p>1.$General$ $weight$ $threshold$ $gates$ can be computed by polynomial size depth 2 circuits built from $majority$ $gates$. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.</p>

<h1>My Question</h1>

<p>$majority$ $gates$ is a monotone gate which is computes a monotone function. A monotone functin does not decreace its function value by increasing the number of "1"s in the input 0-1 bit string. However, $General$ $weight$ $threshold$ $gates$  is NOT a monotone function. For example, we can check the function which output 1 if and only if $2x_{1} -5x_{2} + 3x_{3} \geq 3.5$ is not a monotone function because increasing the value of  $x_{2}$ brokes the monotone property. </p>

<p>My question is :</p>

<p>For a givern arbitrary threshold function $THR:\{0,1\}^{n}\rightarrow \{0,1\}$ with arbitrary real number weights and with no monotonicity, can we construct a constant depth circuit with $poly(n)$ threshold gates such that for any gate, any weight of the gate is integer number and is at most $poly(\Delta) $, where $\Delta$ is fan-in of the gate?</p>

CC BY-SA 3.0
2013-01-17T16:37:08.587Z
In my answer you refer to, when talking about depth 2 circuits built from majority gates I am assuming that inputs to the circuit can be both unnegated as well as negated variables.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-18T10:33:29.703Z
Another related paper that shows that big weights are required (for one thr): http://www.nada.kth.se/~johanh/threshweights.pdf
domotorp
<cc.complexity-theory><circuit-complexity>
Monotonicity and Threshold function
shen
# Monotonicity and Threshold function

(Asked by: username_0 on 2013-01-17)

I have a question about a answer of a question which is proposed in this stack exchange.

# The Past Question

One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma.

Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.

My question is about upper bound of Threshold function which is a natural generalization of majority function.

The formal definition of the threshold function is the following one.

DEFINITION:

$THR(x\_{1},...,x\_{n})=
\begin{cases}
1 & a\_{1}x\_{1}+\cdots +a\_{n}x\_{n} \geq t \\
0 & otherwise
\end{cases}
$

We assume that each weight $a\_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$

QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?

Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .

# Answer

Kristoffer Arnsfelt Hansen said that:

1.$General$ $weight$ $threshold$ $gates$ can be computed by polynomial size depth 2 circuits built from $majority$ $gates$. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.

# My Question

$majority$ $gates$ is a monotone gate which is computes a monotone function. A monotone functin does not decreace its function value by increasing the number of "1"s in the input 0-1 bit string. However, $General$ $weight$ $threshold$ $gates$ is NOT a monotone function. For example, we can check the function which output 1 if and only if $2x\_{1} -5x\_{2} + 3x\_{3} \geq 3.5$ is not a monotone function because increasing the value of $x\_{2}$ brokes the monotone property.

My question is :

For a givern arbitrary threshold function $THR:\{0,1\}^{n}\rightarrow \{0,1\}$ with arbitrary real number weights and with no monotonicity, can we construct a constant depth circuit with $poly(n)$ threshold gates such that for any gate, any weight of the gate is integer number and is at most $poly(\Delta) $, where $\Delta$ is fan-in of the gate?

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: In my answer you refer to, when talking about depth 2 circuits built from majority gates I am assuming that inputs to the circuit can be both unnegated as well as negated variables.  
> **username_2**: Another related paper that shows that big weights are required (for one thr): http://www.nada.kth.se/~johanh/threshweights.pdf  

---

## 1 answers

### Answer by username_3 on 2013-01-18. Score: 2

If I understand your question correctly the answer is yes. In the paper

"Majority Gates Vs. General Weighted Threshold Gates" (http://www.nada.kth.se/~johanh/majorityvsthreshold.pdf) by Goldman, Håstad, and Razborov

They show that anything that can be computed by a depth $d$ threshold circuit can be computed by a depth $d+1$ unweighted threshold circuit of poly size.

Your question seems to be a special case of this for $d=1$.


---

