Arithmetic circuits with just one threshold gate

Question

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 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 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): 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.

---

Answer 1

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.