<p>The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.</p>

<p>First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, and either $ab,a'b\ge t$ as well, or $ab=a'b(=0)$.</p>

<p>With this in mind, we can simulate the circuit with a Boolean monotone circuit by replacing each node $c$ with nodes $c_0,\dots,c_t$, where $c_i$ is intended to compute the predicate $c\ge i$. (We need $c_0$ only for notational convenience, it computes the constant $1$ function.) If $c$ is a Boolean input variable $x$, we take $c_1=x$, $c_2=\dots=c_t=0$. If $c$ is an addition gate, say $c=a+b$, we implement it via
$$c_i=\bigvee_{\substack{j,k\le t\\j+k\ge i}}(a_j\land b_k).$$
Multiplication gates are handled in the same way.</p>

<p>This takes $O(t^3)$ gates per one gate of the original circuit. As a minor optimization, we can reduce it to $O(t^2)$ by putting
\begin{align*}
c_t&amp;=\bigvee_{j+k\ge t}(a_j\land b_k),\\
c_i&amp;=c_{i+1}\lor\bigvee_{j+k=i}(a_j\land b_k),\qquad i&lt;t,
\end{align*}
so that each $a_j\land b_k$ is used as an input of only one of the $c_i$ gates.</p>

CC BY-SA 3.0
2014-11-03T18:21:46.360Z
2014-11-03T18:28:41.303Z
2014-11-03T18:28:41.303Z
Emil Jeřábek
<p>When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a <i>boolean</i> function, we can just add
one fanin-1 threshold gate as the output gate. On input $a\in\{0,1\}^n$, the resulting <i>threshold</i>  $\{+,\times\}$-<i>circuit</i> then outputs $1$ if $F(a)\geq t$,
and outputs $0$ if $F(a)\leq t-1$; the threshold $t=t_n$ can be any positive integer, which may dependent on $n$ but not on input values. The resulting circuit computes some (monotone) <i>boolean</i> function
$F':\{0,1\}^n\to \{0,1\}$.</p>

<blockquote>
<b>Question:</b> Can threshold $\{+,\times\}$-circuits be efficiently simulated by  $\{\lor,\land\}$-circuits?
</blockquote>

<p>Under "efficiently" I mean "with at most a polynomial increase of size."
The answer is clear "yes" for threshold $t=1$: just replace $+$ by $\lor$, $\times$ by $\land$, and remove the last threshold gate. That is, $\{\lor,\land\}$-circuits are in fact threshold-$1$ 
$\{+,\times\}$-circuits.
But what about larger thresholds, say, $t=2$? 
<p></p>

<p>One can define arithmetic analogues $\#C$ of most boolean circuit classes $C$ by just using $+$
instead of OR, $\times$ instead of AND, and $1-x_i$ instead of $\bar{x}_i$. 
For example, $\#AC^0$ circuits
are $\{+,\times\}$-circuits of constant depth with unbounded fanin $+$ and $\times$ gates, and inputs $x_i$ and $1-x_i$. 
<a href="http://www.sciencedirect.com/science/article/pii/S0022000099916756" rel="nofollow">Agrawal, Allender and Datta have shown</a> that  threshold $\#AC^0$ = $TC^0$. (Recall that $AC^0$ itself is a <i>proper</i> subset of $TC^0$; take, say, the Majority function.) In other words, constant-depth threshold circuits can be efficiently simulated by
constant-depth $\{+,-,\times\}$-circuits, with just a single threshold gate! 
Note, however, that my question is about <b>monotone</b> circuits (no Minus "$-$" as gates, and even no $1-x_i$ as inputs). Can one (last) threshold gate be so powerful also then?
I don't know this stuff, so any related pointers are welcome.
<p>
<b>N.B.</b> There is yet another interesting related <a href="http://www.sciencedirect.com/science/article/pii/S0020019097000070" rel="nofollow">result</a>  due to Arnold Rosenbloom: $\{+,\times\}$-circuits with just one <i>monotone</i> function $g:\mathbb{N}^2\to\{0,1\}$ as output gate can compute every slice function with $O(n)$ gates. 
A slice function is a monotone boolean function which, for some fixed $k$, outputs $0$ (resp. $1$) on all inputs with less (resp., more) than $k$ ones. On the other hand, easy counting shows that most slice functions require general $\{\lor,\land,\neg\}$-circuits of exponential size. Thus, one "innocent" additional output gate <i>can</i> make monotone circuits omnipotent! My question asks
whether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate.
<hr>
<b>ACTUALIZATION</b> (added 03.11.2014): Emil Je&#345;&#225;bek has shown (via an amazingly simple construction, see his answer below) that the answer is "yes" as long as  $t\leq n^c$ for a constant $c$.
So, the question remains open only for <b>super-polynomial</b> (in $n$) thresholds.
<p>
Usually, in applications, only large thresholds do work: we usually need thresholds of the form $2^{n^{\epsilon}}$ for $\epsilon &gt; 0$. Say, if $F:\{0,1\}^n\to \mathbb{N}$ <i>counts</i> the number of $s$-$t$ paths in graph specified by the $0$-$1$ input, then for $t=m^{m^2}$ with $m\approx n^{1/3}$, the threshold-$t$ version of $F$ <i>solves</i> the existence of a Hamiltonian $s$-$t$ path problem on $m$-vertex graphs (see, e.g. <a href="http://www.cs.cmu.edu/~flac/pdf/NumberP.pdf" rel="nofollow">here</a>).
<p>
(Added 14.11.2014): Since Emil answered a big portion of my question, and since the case of exponential thresholds is not in sight, I now accept this Emil's (very nice) answer.</p>

<hr>

CC BY-SA 3.0
2014-11-02T21:03:55.540Z
Wait… exponential size?  I think you can implement a slice function in polynomial size with boolean gates, it's just a formula (which cannot re-use intermediate results more than once) that has to be exponential size.
Zsbán Ambrus
CC BY-SA 3.0
2014-11-03T10:24:24.117Z
@ Zsbán Ambrus: There are at most $S^{aS}$ circuits of size $S$, but at least $2^{2^{bn}}$ distinct $k$-slice functions already for $k=n/2$; a,b positive constants.
Stasys
CC BY-SA 3.0
2014-11-03T11:11:04.163Z
Threshold 2, and more generally, thresholds bounded by $2^{n^c}$, can be efficiently simulated by doing the computation in the semiring $(\{0,\dots,t\},\min\{x+y,t\},\min\{xy,t\})$.
Emil Jeřábek
CC BY-SA 3.0
2014-11-03T11:39:06.157Z
Oh, I see now how you defined slice function. Sorry.
Zsbán Ambrus
CC BY-SA 3.0
2014-11-03T12:16:35.583Z
I’ve overstated it a bit: for exponential thresholds, this gives poly-size nonmonotone circuits. If $t$ is polynomially bounded in $n$, one can do it with poly-size monotone circuits.
Emil Jeřábek
CC BY-SA 3.0
2014-11-03T13:46:46.370Z
@Emil Jeřábek: So, from threshold-t {+,x} circuit (t polynomial in n) you can get threshold-1 {+,x} circuit (= {OR, AND} circuit)? (By somehow using unary codes of intermediate results?) Could you sketch this?
Stasys
CC BY-SA 3.0
2014-11-03T15:10:46.550Z
You get $\land,\lor$ circuits directly. Replace each node $c$ with $t+1$ nodes $c_0,\dots,c_t$, where $c_i$ computes the Boolean predicate $c\ge i$. (You don’t need $c_0$ as it computes constant $1$, but it simplifies the expression below.) In this representation, $+$ and $\cdot$ can be simulated by $\{\land,\lor\}$ circuits of size $O(t^2)$: e.g., if $c=a+b$, then $c_i=\bigvee_{j+k\ge i}(a_j\land b_k)$.
Emil Jeřábek
CC BY-SA 3.0
2014-11-03T16:48:54.080Z
@Emil Jeřábek: Very nice! I now added a remark on this. Actually, it may perhaps be worth to put this comment as an answer: polynomial threshold case was also not immediately clear (at least for me).
Stasys
CC BY-SA 3.0
2014-11-03T18:22:16.797Z
OK, I made it an answer.
Emil Jeřábek
CC BY-SA 3.0
2014-11-03T19:07:30.737Z
@Emil Jeřábek: Thanks, Emil, for doing this. I, however, have no idea on how to handle super-polynimal thresholds, as yet.
Stasys
<circuit-complexity><arithmetic-circuits><cc-complexity-theory>
Arithmetic circuits with just one threshold gate
Stasys
# Arithmetic circuits with just one threshold gate

(Asked by: username_0 on 2014-11-02)

When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x\_1,\ldots,x\_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a *boolean* function, we can just add
one fanin-1 threshold gate as the output gate. On input $a\in\{0,1\}^n$, the resulting *threshold* $\{+,\times\}$-*circuit* then outputs $1$ if $F(a)\geq t$,
and outputs $0$ if $F(a)\leq t-1$; the threshold $t=t\_n$ can be any positive integer, which may dependent on $n$ but not on input values. The resulting circuit computes some (monotone) *boolean* function
$F':\{0,1\}^n\to \{0,1\}$.

> **Question:** Can threshold $\{+,\times\}$-circuits be efficiently simulated by $\{\lor,\land\}$-circuits?

Under "efficiently" I mean "with at most a polynomial increase of size."
The answer is clear "yes" for threshold $t=1$: just replace $+$ by $\lor$, $\times$ by $\land$, and remove the last threshold gate. That is, $\{\lor,\land\}$-circuits are in fact threshold-$1$
$\{+,\times\}$-circuits.
But what about larger thresholds, say, $t=2$?

One can define arithmetic analogues $\#C$ of most boolean circuit classes $C$ by just using $+$
instead of OR, $\times$ instead of AND, and $1-x\_i$ instead of $\bar{x}\_i$.
For example, $\#AC^0$ circuits
are $\{+,\times\}$-circuits of constant depth with unbounded fanin $+$ and $\times$ gates, and inputs $x\_i$ and $1-x\_i$.
[Agrawal, Allender and Datta have shown](http://www.sciencedirect.com/science/article/pii/S0022000099916756) that threshold $\#AC^0$ = $TC^0$. (Recall that $AC^0$ itself is a *proper* subset of $TC^0$; take, say, the Majority function.) In other words, constant-depth threshold circuits can be efficiently simulated by
constant-depth $\{+,-,\times\}$-circuits, with just a single threshold gate!
Note, however, that my question is about **monotone** circuits (no Minus "$-$" as gates, and even no $1-x\_i$ as inputs). Can one (last) threshold gate be so powerful also then?
I don't know this stuff, so any related pointers are welcome.

**N.B.** There is yet another interesting related [result](http://www.sciencedirect.com/science/article/pii/S0020019097000070) due to Arnold Rosenbloom: $\{+,\times\}$-circuits with just one *monotone* function $g:\mathbb{N}^2\to\{0,1\}$ as output gate can compute every slice function with $O(n)$ gates.
A slice function is a monotone boolean function which, for some fixed $k$, outputs $0$ (resp. $1$) on all inputs with less (resp., more) than $k$ ones. On the other hand, easy counting shows that most slice functions require general $\{\lor,\land,\neg\}$-circuits of exponential size. Thus, one "innocent" additional output gate *can* make monotone circuits omnipotent! My question asks
whether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate.

---

**ACTUALIZATION** (added 03.11.2014): username_2 has shown (via an amazingly simple construction, see his answer below) that the answer is "yes" as long as $t\leq n^c$ for a constant $c$.
So, the question remains open only for **super-polynomial** (in $n$) thresholds.

Usually, in applications, only large thresholds do work: we usually need thresholds of the form $2^{n^{\epsilon}}$ for $\epsilon > 0$. Say, if $F:\{0,1\}^n\to \mathbb{N}$ *counts* the number of $s$-$t$ paths in graph specified by the $0$-$1$ input, then for $t=m^{m^2}$ with $m\approx n^{1/3}$, the threshold-$t$ version of $F$ *solves* the existence of a Hamiltonian $s$-$t$ path problem on $m$-vertex graphs (see, e.g. [here](http://www.cs.cmu.edu/~flac/pdf/NumberP.pdf)).

(Added 14.11.2014): Since Emil answered a big portion of my question, and since the case of exponential thresholds is not in sight, I now accept this Emil's (very nice) answer.

---

**Tags:** circuit-complexity, arithmetic-circuits, cc-complexity-theory

> **Comments:**
> **username_1**: Wait… exponential size?  I think you can implement a slice function in polynomial size with boolean gates, it's just a formula (which cannot re-use intermediate results more than once) that has to be exponential size.  
> **username_0**: @ username_1: There are at most $S^{aS}$ circuits of size $S$, but at least $2^{2^{bn}}$ distinct $k$-slice functions already for $k=n/2$; a,b positive constants.  
> **username_2**: Threshold 2, and more generally, thresholds bounded by $2^{n^c}$, can be efficiently simulated by doing the computation in the semiring $(\{0,\dots,t\},\min\{x+y,t\},\min\{xy,t\})$.  
> **username_1**: Oh, I see now how you defined slice function. Sorry.  
> **username_2**: I’ve overstated it a bit: for exponential thresholds, this gives poly-size nonmonotone circuits. If $t$ is polynomially bounded in $n$, one can do it with poly-size monotone circuits.  
> **username_0**: @username_2: So, from threshold-t {+,x} circuit (t polynomial in n) you can get threshold-1 {+,x} circuit (= {OR, AND} circuit)? (By somehow using unary codes of intermediate results?) Could you sketch this?  
> **username_2**: You get $\land,\lor$ circuits directly. Replace each node $c$ with $t+1$ nodes $c_0,\dots,c_t$, where $c_i$ computes the Boolean predicate $c\ge i$. (You don’t need $c_0$ as it computes constant $1$, but it simplifies the expression below.) In this representation, $+$ and $\cdot$ can be simulated by $\{\land,\lor\}$ circuits of size $O(t^2)$: e.g., if $c=a+b$, then $c_i=\bigvee_{j+k\ge i}(a_j\land b_k)$.  
> **username_0**: @username_2: Very nice! I now added a remark on this. Actually, it may perhaps be worth to put this comment as an answer: polynomial threshold case was also not immediately clear (at least for me).  
> **username_2**: OK, I made it an answer.  
> **username_0**: @username_2: Thanks, Emil, for doing this. I, however, have no idea on how to handle super-polynimal thresholds, as yet.  

---

## 1 answers

### Answer by username_2 on 2014-11-03. Score: 16 | Accepted answer

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.

First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, and either $ab,a'b\ge t$ as well, or $ab=a'b(=0)$.

With this in mind, we can simulate the circuit with a Boolean monotone circuit by replacing each node $c$ with nodes $c\_0,\dots,c\_t$, where $c\_i$ is intended to compute the predicate $c\ge i$. (We need $c\_0$ only for notational convenience, it computes the constant $1$ function.) If $c$ is a Boolean input variable $x$, we take $c\_1=x$, $c\_2=\dots=c\_t=0$. If $c$ is an addition gate, say $c=a+b$, we implement it via
$$c\_i=\bigvee\_{\substack{j,k\le t\\j+k\ge i}}(a\_j\land b\_k).$$
Multiplication gates are handled in the same way.

This takes $O(t^3)$ gates per one gate of the original circuit. As a minor optimization, we can reduce it to $O(t^2)$ by putting
\begin{align\*}
c\_t&=\bigvee\_{j+k\ge t}(a\_j\land b\_k),\\
c\_i&=c\_{i+1}\lor\bigvee\_{j+k=i}(a\_j\land b\_k),\qquad i


---

