When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes somefunction $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just addone 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$ circuitsare $\{+,\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 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 byconstant-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  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 askswhether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate.ACTUALIZATION (added 03.11.2014): Emil Jeřá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 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).(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.
Arithmetic circuits with just one threshold gate
circuit complexity;arithmetic circuits;cc complexity theory
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<t,\end{align*}so that each $a_j\land b_k$ is used as an input of only one of the $c_i$ gates.