As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the VC dimension of polynomials over the tropical semirings (see Theorem 2 below).
Let $R$ be a semiring. A zero-pattern of a sequence $(f_1,\ldots,f_m)$ of $m$ polynomials in $R[x_1,\ldots,x_n]$ is a subset $S\subseteq \{1,\ldots,m\}$ for which there exist $x\in R^n$ and $y\in R$ such that for all $i=1,\ldots,m$, $f_i(x)= y$ iff $i\in S$. That is, the graphs of exactly those polynomials $f_i$ with $i\in S$ must hit the point $(x,y)\in R^{n+1}$. ("Zero-pattern" because the condition $f_i(x)=y$ can be replaced by $f_i(x)-y=0$.) Let $Z(m)$ = the maximum possible number of zero-patterns of a sequence of $m$ polynomials of degree at most $d$. Hence, $0\leq Z(m)\leq 2^m$. The Vapnik-Chervonenkis dimension of degree $d$ polynomials is $VC(n,d) := \max\{m\colon Z(m)=2^m\}$.
Remark: Usually, the VC dimension is defined for a family ${\cal F}$ of sets as the largest cardinality $|S|$ of a set $S$ such that $\{F\cap S\colon F\in{\cal F}\}=2^S$. To fit into this frame, we can associate with every pair $(x,y)\in R^{n+1}$ the set $F_{x,y}$ of all polynomials of $f$ degree $\leq d$ for which $f(x)=y$ holds. Then the VC dimension of the family ${\cal F}$ of all such sets $F_{x,y}$ is exactly $VC(n,d)$.
A trivial upper bound on $m=VC(n,d)$ is $m\leq n\log |R|$ (we need at least $2^m$ distinct vectors $x\in R^n$ to have all $2^m$ possible patterns), but it is useless in infinite semirings. To have good upper bounds on the VC dimension, we need good upper bounds on $Z(m)$. Over fields, such bounds are known.
Theorem 1: Over any field $R$, we have $Z(m)\leq \binom{md+n}{n}$.Similar upper bounds were earlier proved by Milnor, Heintz and Warren; their proofs use heavy techniques from real algebraic geometry. In contrast, a half-page proof of Theorem 1 by Ronyai, Babai and Ganapathy (which we give below) is a simple application of linear algebra.
By looking for small $m$'s satisfying $\binom{md+n}{n} < 2^m$, we obtain that $VC(n,d)=O(n\log d)$ holds over any field. In view of the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$, important here is that the dimension is only logarithmic in the degree $d$. This is important because circuits of polynomial size can compute polynomials of exponential degree, and because a result of Haussler in PAC learning (Corollary 2 on page 114 of this paper) yields the following (where we assume that deterministic circuits are allowed to use majority vote to output their values).
Theorem 2: $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ holds for circuits over any semiring $R$, where $VC(n,d)$ is only polynomial in $n$ and $\log d$.See here on how Haussler's result implies Theorem 2.
In particular, by Theorem 1, $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ holds over any field. (Interesting is here only the case of infinite fields: for finite ones, much simpler arguments work: Chernoff bound then does the work.) But what about (infinite) semirings that are not fields, or even not rings? Motivated by dynamic programming, I am mainly interested in tropical $(\max,+)$ and $(\min,+)$ semirings, but other "non-field" (infinite) semirings are interesting as well. Note that, over the $(\max,+)$ semiring, a polynomial $f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$ with $A\subseteq\mathbb{N}$ and $c_a\in \mathbb{R}$, turns into the maximization problem $f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$; the degree of $f$ is (as customary) the maximum of $a_1+\cdots+a_n$ over all $a\in A$.
Question : Is the VC dimension of degree $\leq d$ polynomials over tropical semirings polynomial in $n\log d$?
I admit, this can be a rather hard question to expect a quick answer: tropical algebra is rather "crazy". But perhaps somebody has some ideas on why (if any) tropical polynomials could produce more zero-patterns than real polynomials? Or why they "shouldn't"? Or some related references.
Or, perhaps, the proof of Babai, Ronyai, and Ganapathy (below) can be somehow "twisted" to work over tropical semirings? Or over any other infinite semirings (which are not fields)?
Proof of Theorem 1: Assume that a sequence $(f_1,\ldots,f_m)$ has $p$ different zero-patterns, and let $v_1,\ldots,v_p\in R^n$ be witnesses to these zero-patterns. Let $S_i=\{k\colon f_k(v_i)\neq 0\}$ be a zero-pattern witnessed by the $i$-th vector $v_i$, and consider the polynomials $g_i:=\prod_{k\in S_i}f_k$. We claim that these polynomials are linearly independent over our field. This claim completes the proof of the theorem since each $g_i$ has degree at most $D:=md$, and the dimension of the space of polynomials of degree at most $D$ is $\binom{n+D}{D}$. To prove the claim, it is enough to note that $g_i(v_j)\neq 0$ if and only if $S_i\subseteq S_j$. Suppose contrariwise that a nontrivial linear relation $\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$ exists. Let $j$ be a subscript such that $|S_j|$ is minimal among the $S_i$ with $\lambda_i\neq 0$. Substitute $v_j$ in the relation. While $\lambda_jg_j(v_j)\neq 0$, we have $\lambda_ig_i(v_j)=0$ for all $i\neq j$, a contradiction. $\Box$
