<p>This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while constraining the randomness to a finite domain might actually trivialize the question of whether Adleman's theorem holds.</p>

<p>Suppose you're working over the complex numbers $\mathbb{C}$, so that circuits compute polynomials over that field, and suppose the function $f$ is itself computed by some polynomial (however complicated) of the $x$ variables. Then it turns out that already for some fixed $r$, $C(x,r) = f(x)$. The reason is that for each $r$, the set of $x$ with $C(x,r) = f(x)$ determines a Zariski-closed subset of $\mathbb{C}^n$, and so must be all of $\mathbb{C}^n$, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many $r$'s in consideration, the set of $x$ where $\exists r : C(x,r) = f(x)$ would also have measure zero. On the other hand, the assumption that $C$ computes $f$ implies this that set must be all of $\mathbb{C}^n$, so it cannot have measure zero.</p>

CC BY-SA 3.0
2017-02-27T18:24:08.267Z
Interesting. More generally, a probabilistic circuit of size M is some  random variable C taking its values in the set of all circuits (of that type) with at most M gates. [B.t.w. that paper of Cucker at al. allows C be arbitrarily distributed. The "majority trick" stil works.] Can I conclude from your argument that, if the range of C is finite, then Adleman's theorem is trivial when Zarinski-closed subsets are either trivial (sets themselves) or have zero measure? Have we this - "all or nothing" - effect in tropical semirings? (I am mainly interested in them.)
Stasys
CC BY-SA 3.0
2017-02-27T20:19:51.993Z
I don't know how or whether the argument would generalize to other semirings, sorry. One main thing that's missing (for me) is the geometric intuition akin to how "polynomials that disagree" translates to "measure-zero subsets of $\mathbb{C}^n$". For tropical semirings in particular, the operations seem so different from ordinary polynomials that it's hard to even guess at what the appropriate adaptation ought to be.
Andrew Morgan
CC BY-SA 3.0
2017-02-27T17:36:01.600Z
2017-02-27T17:36:01.600Z
Andrew Morgan
<p>Adleman has shown in 1978 that <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span>: if a boolean function <span class="math-container">$f$</span> of <span class="math-container">$n$</span> variables can be computed by a probabilistic boolean circuit of size <span class="math-container">$M$</span>, then <span class="math-container">$f$</span> can be also computed by a deterministic boolean circuit of size polynomial in <span class="math-container">$M$</span> and <span class="math-container">$n$</span>; actually, of size <span class="math-container">$O(nM)$</span>.</p>
 <blockquote>
<b>General Question :</b> Over what other (than boolean) semirings
does <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span> hold?
</blockquote>
 
To be a bit more specific, a <i>probabilistic</i> circuit <span class="math-container">$\mathsf{C}$</span>  over a semiring <span class="math-container">$(S,+,\cdot,0,1)$</span> uses its "addition" <span class="math-container">$(+)$</span> and "multiplication'' <span class="math-container">$(\cdot)$</span> operations as gates. Inputs are input variables <span class="math-container">$x_1,\ldots,x_n$</span> and possibly some number of additional random variables, which take
the values <span class="math-container">$0$</span> and <span class="math-container">$1$</span>
independently with probability <span class="math-container">$1/2$</span>; here <span class="math-container">$0$</span>  and <span class="math-container">$1$</span> are, respectively, the additive and multiplicative identities of the semiring. Such a circuit <span class="math-container">$\mathsf{C}$</span> <i>computes</i> a given function <span class="math-container">$f:S^n\to S$</span> if for every <span class="math-container">$x\in S^n$</span>, <span class="math-container">$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$</span>.
<p>
The <i>voting function</i> <span class="math-container">$\mathrm{Maj}(y_1,\ldots,y_m)$</span> of <span class="math-container">$m$</span> variables is a partial function whose value is <span class="math-container">$y$</span> if the element <span class="math-container">$y$</span> appears more than <span class="math-container">$m/2$</span> times among the <span class="math-container">$y_1,\ldots,y_m$</span>, and is undefined, if no such element <span class="math-container">$y$</span> exists. A simple application of Chernoff's and union bounds yields the following.
<blockquote>
<b>Majority Trick:</b> If a probabilistic circuit <span class="math-container">$\mathsf{C}$</span> computes a function <span class="math-container">$f:S^n\to S$</span> on a finite set <span class="math-container">$X\subseteq S^n$</span>, then there are <span class="math-container">$m=O(\log|X|)$</span> realizations <span class="math-container">$C_1,\ldots,C_m$</span> of <span class="math-container">$\mathsf{C}$</span> such that <span class="math-container">$f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$</span> holds for all <span class="math-container">$x\in X$</span>.
</blockquote>
Over the boolean semiring, the voting function <span class="math-container">$\mathrm{Maj}$</span> is the majority function, and has small (even monotone) circuits. So, Adleman's theorem follows by taking <span class="math-container">$X=\{0,1\}^n$</span>.
<p>
But what about other (especially, infinite) semirings? What about the <i>arithmetic</i> semiring <span class="math-container">$(\mathbb{N},+,\cdot,0,1)$</span> (with usual addition and multiplication)?
<blockquote>
<b>Question 1:</b> Does <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span> hold over the arithmetic semiring?
</blockquote>
Although I bet for "yes", I cannot show this. 
<p>
<b>Remark:</b> I am aware of this <a href="https://web.vu.lt/mif/s.jukna/boolean/random-circuits.pdf" rel="nofollow noreferrer">paper</a> where the authors claim <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span> over the real field <span class="math-container">$(\mathbb{R},+,\cdot,0,1)$</span>. They deal with <i>non-monotone</i> arithmetic circuits, and also arrive (in Theorem 4) to circuits with  the voting function <span class="math-container">$\mathrm{Maj}$</span> as an output gate. But how to simulate this <span class="math-container">$\mathrm{Maj}$</span>-gate by an arithmetic circuit (be it monotone or not)? I.e. how to get their Corollary 3? 
<p>Actually, the following simple argument told to me by Sergey Gashkov (from Moscow University) seems to show that this is <i>impossible</i> (at least for circuits able to compute only <i>polynomials</i>). Suppose we can express <span class="math-container">$\mathrm{Maj}(x,y,z)$</span> as a polynomial <span class="math-container">$f(x,y,z)=ax+by+cz+ h(x,y,z)$</span>. Then <span class="math-container">$f(x,x,z)=x$</span> implies <span class="math-container">$c=0$</span>,
<span class="math-container">$f(x,y,x)=x$</span> implies <span class="math-container">$b=0$</span>, and <span class="math-container">$f(x,y,y)=y$</span> implies <span class="math-container">$a=0$</span>.
This holds because, over fields of zero characteristic, equality of polynomial-functions means equality of coefficients.
Note that in Question 1, the range of probabilistic circuits, and hence, the domain of
the <span class="math-container">$\mathrm{Maj}$</span>-gate is <i>infinite</i>. I therefore have an impression that the linked paper deals only with arithmetic circuits computing functions <span class="math-container">$f:\mathbb{R}^n\to Y$</span> with small finite ranges <span class="math-container">$Y$</span>, like <span class="math-container">$Y=\{0,1\}$</span>. Then <span class="math-container">$\mathrm{Maj}:Y^m\to Y$</span> is indeed easy to compute by an arithmetic circuit. But what if <span class="math-container">$Y=\mathbb{R}$</span>?</p>
<hr>
<b>Correction</b> [6.03.2017]: Pascal Koiran (one of the authors of this paper) pointed to me that their model is more powerful than just arithmetic circuits: they allow Sign-gates (outputing <span class="math-container">$0$</span> or <span class="math-container">$1$</span> depending on whether the input is negative of not). So, the voting function Maj <i>can</i> be simulated in this model, and I take back my "confusion". 
<hr>
<p>
In the context of dynamic programming, especially interesting is the same question for  <i>tropical</i> min-plus and max-plus semirings <span class="math-container">$(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$</span>
and  <span class="math-container">$(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$</span>.
<blockquote>
<b>Question 2:</b> Does <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span> hold over tropical semirings?
</blockquote>
 Held <span class="math-container">$\mathrm{BPP}\subseteq \mathrm{P/poly}$</span> in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms <i>are</i> pure.
<p>
So far, I can only answer Question 2 (affirmatively) under the <i>one-sided</i> error scenario, when we additionally require
<span class="math-container">$\mathrm{Pr}[\mathsf{C}(x) &lt; f(x)]=0$</span>
over the min-plus semiring (minimization), or 
<span class="math-container">$\mathrm{Pr}[\mathsf{C}(x) &gt; f(x)]=0$</span> over the max-plus semiring (maximization). That is, we now require that the the randomized tropical circuit can never produce any better than optimum value; it can, however, err by giving some worse-than-optimal values.  My questions are, however, under the <i>two-sided error</i> scenario. 
<hr>
<b>P.S.</b> [added 27.02.2017]: <a href="https://web.vu.lt/mif/s.jukna/ftp/adleman2.html" rel="nofollow noreferrer"><b>Here</b></a> is my attempt to answer Question 1 (affirmatively). The idea is to combine a simplest version of the "combinatorial Nullstellensatz" with an estimate for the Zarankiewicz problem for n-partite hypergraps, due to Erdos and Spencer. Modulo this latter result, the entire argument is elementary.
<p>
Note that Question 2 still remains open: the "naive Nullstellensatz" (at least in the form I used) does not hold in tropical semirings. 

CC BY-SA 3.0
2017-02-25T21:46:08.630Z
nit: BPP is a uniform class defined using PTMs not circuits.
Kaveh
CC BY-SA 3.0
2017-02-26T09:31:37.880Z
@Kaveh: yes, in this sense, Adleman's result is even a bit stronger, it holds even for BPP/poly.
Stasys
CC BY-SA 3.0
2017-02-27T03:33:55.817Z
Don't see how the simple argument shows impossibility... it does seem to show that the coefficients of the x, y, and z monomials must be zero... what am I missing? Also, if a polynomial can't compute Maj, how else can you representing a computation over a semiring? (What else besides a polynomial over the semiring?) Intuitively, over an infinite domain, each constraint on some y (enforcing that on >m/2 y's you must output y) seems "independent" of the others (no subset of constraints implies another) so it seems no "finite" polynomial could satisfy the infinitely many independent constraints.
Ryan Williams
CC BY-SA 3.0
2017-02-27T12:03:55.880Z
@Ryan: yes, this only shows f=Maj implies h=Maj. But h has degree > 1, so  h(x,x,z)=x is impossible. And you are right: circuits over semirings cannot compute anything else as polynomials. So, they cannot compute Maj. But the authors of that paper deal with {+,x,-,/} circuits, with all field operations allowed. Perhaps then Maj can still be somehow computed? (I however, do not see how.) B.t.w. instead of trying to simulate Maj itself, one could answer Q1&Q2 by showing that one Maj-gate cannot substantially decrease circuit size (which is quite plausible).
Stasys
CC BY-SA 3.0
2017-03-02T14:20:29.180Z
@Ryan: P.S. Igor Sergeev observed that Maj "could" be probable computable over (R,+,x,-,/). E.g. Maj(x,y,z) is computable by f(x,y,z)=(xy+xz-2yz)/(2x-y-z) for all inputs with |{x,y,z}|=2. Note that the simple argument above implies that, already on such inputs, this cannot be done over (R,+,x,-). So, division can help. But we face the division by 0 issue ...
Stasys
<cc.complexity-theory><circuit-complexity><randomized-algorithms><derandomization><arithmetic-circuits>
Adleman's theorem over infinite semirings?
Stasys
# Adleman's theorem over infinite semirings?

(Asked by: username_0 on 2017-02-25)

Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also computed by a deterministic boolean circuit of size polynomial in $M$ and $n$; actually, of size $O(nM)$.

> **General Question :** Over what other (than boolean) semirings
> does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold?

To be a bit more specific, a *probabilistic* circuit $\mathsf{C}$ over a semiring $(S,+,\cdot,0,1)$ uses its "addition" $(+)$ and "multiplication'' $(\cdot)$ operations as gates. Inputs are input variables $x\_1,\ldots,x\_n$ and possibly some number of additional random variables, which take
the values $0$ and $1$
independently with probability $1/2$; here $0$ and $1$ are, respectively, the additive and multiplicative identities of the semiring. Such a circuit $\mathsf{C}$ *computes* a given function $f:S^n\to S$ if for every $x\in S^n$, $\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$.

The *voting function* $\mathrm{Maj}(y\_1,\ldots,y\_m)$ of $m$ variables is a partial function whose value is $y$ if the element $y$ appears more than $m/2$ times among the $y\_1,\ldots,y\_m$, and is undefined, if no such element $y$ exists. A simple application of Chernoff's and union bounds yields the following.
> **Majority Trick:** If a probabilistic circuit $\mathsf{C}$ computes a function $f:S^n\to S$ on a finite set $X\subseteq S^n$, then there are $m=O(\log|X|)$ realizations $C\_1,\ldots,C\_m$ of $\mathsf{C}$ such that $f(x)=\mathrm{Maj}(C\_1(x),\ldots,C\_m(x))$ holds for all $x\in X$.

Over the boolean semiring, the voting function $\mathrm{Maj}$ is the majority function, and has small (even monotone) circuits. So, Adleman's theorem follows by taking $X=\{0,1\}^n$.

But what about other (especially, infinite) semirings? What about the *arithmetic* semiring $(\mathbb{N},+,\cdot,0,1)$ (with usual addition and multiplication)?
> **Question 1:** Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over the arithmetic semiring?

Although I bet for "yes", I cannot show this.

**Remark:** I am aware of this [paper](https://web.vu.lt/mif/s.jukna/boolean/random-circuits.pdf) where the authors claim $\mathrm{BPP}\subseteq \mathrm{P/poly}$ over the real field $(\mathbb{R},+,\cdot,0,1)$. They deal with *non-monotone* arithmetic circuits, and also arrive (in Theorem 4) to circuits with the voting function $\mathrm{Maj}$ as an output gate. But how to simulate this $\mathrm{Maj}$-gate by an arithmetic circuit (be it monotone or not)? I.e. how to get their Corollary 3?

Actually, the following simple argument told to me by Sergey Gashkov (from Moscow University) seems to show that this is *impossible* (at least for circuits able to compute only *polynomials*). Suppose we can express $\mathrm{Maj}(x,y,z)$ as a polynomial $f(x,y,z)=ax+by+cz+ h(x,y,z)$. Then $f(x,x,z)=x$ implies $c=0$,
$f(x,y,x)=x$ implies $b=0$, and $f(x,y,y)=y$ implies $a=0$.
This holds because, over fields of zero characteristic, equality of polynomial-functions means equality of coefficients.
Note that in Question 1, the range of probabilistic circuits, and hence, the domain of
the $\mathrm{Maj}$-gate is *infinite*. I therefore have an impression that the linked paper deals only with arithmetic circuits computing functions $f:\mathbb{R}^n\to Y$ with small finite ranges $Y$, like $Y=\{0,1\}$. Then $\mathrm{Maj}:Y^m\to Y$ is indeed easy to compute by an arithmetic circuit. But what if $Y=\mathbb{R}$?

---

**Correction** [6.03.2017]: Pascal Koiran (one of the authors of this paper) pointed to me that their model is more powerful than just arithmetic circuits: they allow Sign-gates (outputing $0$ or $1$ depending on whether the input is negative of not). So, the voting function Maj *can* be simulated in this model, and I take back my "confusion".

---

In the context of dynamic programming, especially interesting is the same question for *tropical* min-plus and max-plus semirings $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$
and $(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$.
> **Question 2:** Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over tropical semirings?

Held $\mathrm{BPP}\subseteq \mathrm{P/poly}$ in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms *are* pure.

So far, I can only answer Question 2 (affirmatively) under the *one-sided* error scenario, when we additionally require
$\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$
over the min-plus semiring (minimization), or
$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$ over the max-plus semiring (maximization). That is, we now require that the the randomized tropical circuit can never produce any better than optimum value; it can, however, err by giving some worse-than-optimal values. My questions are, however, under the *two-sided error* scenario.

---

**P.S.** [added 27.02.2017]: [**Here**](https://web.vu.lt/mif/s.jukna/ftp/adleman2.html) is my attempt to answer Question 1 (affirmatively). The idea is to combine a simplest version of the "combinatorial Nullstellensatz" with an estimate for the Zarankiewicz problem for n-partite hypergraps, due to Erdos and Spencer. Modulo this latter result, the entire argument is elementary.

Note that Question 2 still remains open: the "naive Nullstellensatz" (at least in the form I used) does not hold in tropical semirings.

**Tags:** cc.complexity-theory, circuit-complexity, randomized-algorithms, derandomization, arithmetic-circuits
> **Comments:**
> **username_1**: nit: BPP is a uniform class defined using PTMs not circuits.  
> **username_0**: @Kaveh: yes, in this sense, Adleman's result is even a bit stronger, it holds even for BPP/poly.  
> **username_2**: Don't see how the simple argument shows impossibility... it does seem to show that the coefficients of the x, y, and z monomials must be zero... what am I missing? Also, if a polynomial can't compute Maj, how else can you representing a computation over a semiring? (What else besides a polynomial over the semiring?) Intuitively, over an infinite domain, each constraint on some y (enforcing that on >m/2 y's you must output y) seems "independent" of the others (no subset of constraints implies another) so it seems no "finite" polynomial could satisfy the infinitely many independent constraints.  
> **username_0**: @Ryan: yes, this only shows f=Maj implies h=Maj. But h has degree > 1, so  h(x,x,z)=x is impossible. And you are right: circuits over semirings cannot compute anything else as polynomials. So, they cannot compute Maj. But the authors of that paper deal with {+,x,-,/} circuits, with all field operations allowed. Perhaps then Maj can still be somehow computed? (I however, do not see how.) B.t.w. instead of trying to simulate Maj itself, one could answer Q1&Q2 by showing that one Maj-gate cannot substantially decrease circuit size (which is quite plausible).  
> **username_0**: @Ryan: P.S. Igor Sergeev observed that Maj "could" be probable computable over (R,+,x,-,/). E.g. Maj(x,y,z) is computable by f(x,y,z)=(xy+xz-2yz)/(2x-y-z) for all inputs with |{x,y,z}|=2. Note that the simple argument above implies that, already on such inputs, this cannot be done over (R,+,x,-). So, division can help. But we face the division by 0 issue ...  

---

## 1 answers

### Answer by username_3 on 2017-02-27. Score: 3

This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while constraining the randomness to a finite domain might actually trivialize the question of whether Adleman's theorem holds.

Suppose you're working over the complex numbers $\mathbb{C}$, so that circuits compute polynomials over that field, and suppose the function $f$ is itself computed by some polynomial (however complicated) of the $x$ variables. Then it turns out that already for some fixed $r$, $C(x,r) = f(x)$. The reason is that for each $r$, the set of $x$ with $C(x,r) = f(x)$ determines a Zariski-closed subset of $\mathbb{C}^n$, and so must be all of $\mathbb{C}^n$, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many $r$'s in consideration, the set of $x$ where $\exists r : C(x,r) = f(x)$ would also have measure zero. On the other hand, the assumption that $C$ computes $f$ implies this that set must be all of $\mathbb{C}^n$, so it cannot have measure zero.

> **Comments:**
> **username_0**: Interesting. More generally, a probabilistic circuit of size M is some  random variable C taking its values in the set of all circuits (of that type) with at most M gates. [B.t.w. that paper of Cucker at al. allows C be arbitrarily distributed. The "majority trick" stil works.] Can I conclude from your argument that, if the range of C is finite, then Adleman's theorem is trivial when Zarinski-closed subsets are either trivial (sets themselves) or have zero measure? Have we this - "all or nothing" - effect in tropical semirings? (I am mainly interested in them.)  
> **username_3**: I don't know how or whether the argument would generalize to other semirings, sorry. One main thing that's missing (for me) is the geometric intuition akin to how "polynomials that disagree" translates to "measure-zero subsets of $\mathbb{C}^n$". For tropical semirings in particular, the operations seem so different from ordinary polynomials that it's hard to even guess at what the appropriate adaptation ought to be.  

---

