21
$\begingroup$

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.


$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zsbán Ambrus Nov 2 '14 at 21:03
  • $\begingroup$ @ 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. $\endgroup$ – Stasys Nov 3 '14 at 10:24
  • $\begingroup$ 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\})$. $\endgroup$ – Emil Jeřábek supports Monica Nov 3 '14 at 11:11
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek supports Monica Nov 3 '14 at 15:10
  • 1
    $\begingroup$ @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). $\endgroup$ – Stasys Nov 3 '14 at 16:48
16
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.