<ol>
<li><p>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 <a href="http://dx.doi.org/10.1007/11549345_11">Amano and Maruoka</a>. Then you can just compute each of these by constant depth circuits built from AND and OR gates.</p></li>
<li><p>You can always assume weights are integers of magnitude at most $(n+1)^{(n+1)/2}/2^n$. See <a href="http://dx.doi.org/10.1016/0016-0032%2861%2990702-5">Muroga, Toda and Takasu</a></p></li>
</ol>

CC BY-SA 3.0
2012-10-12T10:45:16.750Z
2012-10-12T10:45:16.750Z
Kristoffer Arnsfelt Hansen
<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>

<p>QUESTION2</p>

<p>Can we $\textit{relax}$ the assumption that   $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$ ?</p>

<p>For example, even if we assume that  $a_{i} \in \mathbb{R}$ is at most $2^{2^{O(n)}}$ and give the strong power of each threshold gate, does uppwer bounds  $2^{n^{\epsilon}}$  holds ? </p>

<cc.complexity-theory><circuit-complexity>
Constant Depth Circuit Computing Threshold Function
Elely
# Constant Depth Circuit Computing Threshold Function

(Asked by: username_0 on 2012-10-12)

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}}$ .

QUESTION2

Can we $\textit{relax}$ the assumption that $a\_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$ ?

For example, even if we assume that $a\_{i} \in \mathbb{R}$ is at most $2^{2^{O(n)}}$ and give the strong power of each threshold gate, does uppwer bounds $2^{n^{\epsilon}}$ holds ?

**Tags:** cc.complexity-theory, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2012-10-12. Score: 7

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](http://dx.doi.org/10.1007/11549345_11). Then you can just compute each of these by constant depth circuits built from AND and OR gates.
2. You can always assume weights are integers of magnitude at most $(n+1)^{(n+1)/2}/2^n$. See [Muroga, Toda and Takasu](http://dx.doi.org/10.1016/0016-0032%2861%2990702-5)


---

