<p>I've realized that the answer to my question is - yes: the VC dimension of degree <span class="math-container">$\leq d$</span> polynomials on <span class="math-container">$n$</span> variables over any tropical semiring is at most a constant times <span class="math-container">$n^2\log(n+d)$</span>. This can be shown using Theorem 1 above.  See <a href="https://web.vu.lt/mif/s.jukna/ftp/tropical-vc-dim.html" rel="nofollow noreferrer">here</a>
for details. So, <b>BPP</b> <span class="math-container">$\subseteq$</span> <b>P/poly</b> holds also for tropical circuits and, hence, also for &quot;pure&quot; dynamic programming algorithms.</p>
<hr>
<b>N.B.</b> (added 25.06.2019) In the mean time, I've resolved the problem <b>completely</b> in <a href="https://web.vu.lt/mif/s.jukna/ftp/derandDP.pdf" rel="nofollow noreferrer">this paper</a>. In such a generality, which I haven't even dreamed at the beginning. Tropical case is here just a very, very special case. And even more curiously:  by just an appropriate combination of already know (deep in any respect) results of other authors.
<p>What remains else to do in this (BPP vs. P/poly) direction? Besides the decrease of the size of resulting deterministic circuits (an interesting question in itself).</p>

CC BY-SA 4.0
2017-03-24T20:53:53.277Z
2022-01-02T13:41:18.057Z
2022-01-02T13:41:18.057Z
Stasys
<p>As in <a href="https://cstheory.stackexchange.com/questions/37632/adlemans-theorem-over-infinite-semirings">this</a> question, I am interested the <span class="math-container">$\mathbf{BPP}$</span> vs. <span class="math-container">$\mathbf{P}$</span>/<span class="math-container">$\mathrm{poly}$</span> <a href="https://en.wikipedia.org/wiki/P/poly" rel="nofollow noreferrer">problem</a> for <i>tropical</i> <span class="math-container">$(\max,+)$</span> and <span class="math-container">$(\min,+)$</span> circuits.  This question reduces to showing upper bounds for the VC dimension of polynomials over the tropical semirings (see Theorem 2 below).</p>
<p>
Let <span class="math-container">$R$</span> be a semiring.
A <i>zero-pattern</i> of a sequence <span class="math-container">$(f_1,\ldots,f_m)$</span> of <span class="math-container">$m$</span> polynomials in <span class="math-container">$R[x_1,\ldots,x_n]$</span> is a subset <span class="math-container">$S\subseteq \{1,\ldots,m\}$</span> for which there exist <span class="math-container">$x\in R^n$</span> and <span class="math-container">$y\in R$</span> such that for all <span class="math-container">$i=1,\ldots,m$</span>,  <span class="math-container">$f_i(x)= y$</span> iff <span class="math-container">$i\in S$</span>. That is, the graphs of exactly those polynomials <span class="math-container">$f_i$</span> with <span class="math-container">$i\in S$</span> must hit the point <span class="math-container">$(x,y)\in R^{n+1}$</span>. ("Zero-pattern" because the condition <span class="math-container">$f_i(x)=y$</span> can be replaced by <span class="math-container">$f_i(x)-y=0$</span>.) 
Let <span class="math-container">$Z(m)$</span> = the maximum possible number of zero-patterns of a sequence of <span class="math-container">$m$</span> polynomials of degree at most <span class="math-container">$d$</span>. Hence, <span class="math-container">$0\leq Z(m)\leq 2^m$</span>. The  <i>Vapnik-Chervonenkis dimension</i> of degree <span class="math-container">$d$</span> polynomials is
<span class="math-container">$VC(n,d) := \max\{m\colon Z(m)=2^m\}$</span>.
<p>
<b>Remark:</b> Usually, the VC dimension is defined for a family <span class="math-container">${\cal F}$</span> of sets as the largest cardinality <span class="math-container">$|S|$</span> of a set <span class="math-container">$S$</span> such that <span class="math-container">$\{F\cap S\colon F\in{\cal F}\}=2^S$</span>. To fit into this frame, we can associate with every pair <span class="math-container">$(x,y)\in R^{n+1}$</span> the set <span class="math-container">$F_{x,y}$</span> of all polynomials of <span class="math-container">$f$</span> degree <span class="math-container">$\leq d$</span> for which <span class="math-container">$f(x)=y$</span> holds. Then the VC dimension of the family <span class="math-container">${\cal F}$</span> of all such sets <span class="math-container">$F_{x,y}$</span> is exactly <span class="math-container">$VC(n,d)$</span>.
<p>
A trivial upper bound on <span class="math-container">$m=VC(n,d)$</span> is <span class="math-container">$m\leq n\log |R|$</span> (we need at least <span class="math-container">$2^m$</span> distinct vectors <span class="math-container">$x\in R^n$</span> to have all <span class="math-container">$2^m$</span> possible patterns), but it is useless in infinite semirings. To have good upper bounds on the VC dimension, we need good upper bounds on <span class="math-container">$Z(m)$</span>.
Over <i>fields</i>, such bounds are known.
 <blockquote>
<b>Theorem 1:</b>  Over any <i>field</i> <span class="math-container">$R$</span>, we have <span class="math-container">$Z(m)\leq \binom{md+n}{n}$</span>.
</blockquote>
Similar upper bounds were earlier proved by 
<a href="http://www.ams.org/journals/proc/1964-015-02/S0002-9939-1964-0161339-9/" rel="nofollow noreferrer">Milnor</a>, <a href="http://www.sciencedirect.com/science/article/pii/0304397583900026" rel="nofollow noreferrer">Heintz</a> and 
<a href="http://www.ams.org/journals/tran/1968-133-01/S0002-9947-1968-0226281-1/" rel="nofollow noreferrer">Warren</a>;
their proofs use heavy techniques from real algebraic geometry.
In contrast, a half-page proof of Theorem 1 by <a href="http://www.ams.org/journals/jams/2001-14-03/S0894-0347-01-00367-8/" rel="nofollow noreferrer">Ronyai, Babai and Ganapathy</a> (which we give below) is a simple application of linear algebra. 
<p>
<p>By looking for small <span class="math-container">$m$</span>'s satisfying <span class="math-container">$\binom{md+n}{n} &lt; 2^m$</span>, we obtain that  <span class="math-container">$VC(n,d)=O(n\log d)$</span> holds  over any <i>field</i>.
In view of the <span class="math-container">$\mathbf{BPP}$</span> vs. <span class="math-container">$\mathbf{P}$</span>/<span class="math-container">$\mathrm{poly}$</span>,
important here is that the dimension is only <i>logarithmic</i> in the degree <span class="math-container">$d$</span>. 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 <a href="http://www.sciencedirect.com/science/article/pii/089054019290010D" rel="nofollow noreferrer">this paper</a>) yields the following (where we assume that deterministic circuits are allowed to use majority vote to output their values).</p>
 <blockquote>
<b>Theorem 2:</b> <span class="math-container">$\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$</span> holds for circuits over any semiring <span class="math-container">$R$</span>, where <span class="math-container">$VC(n,d)$</span>  is only polynomial in <span class="math-container">$n$</span> and <span class="math-container">$\log d$</span>.
</blockquote>
See <a href="https://web.vu.lt/mif/s.jukna/ftp/haussler.html" rel="nofollow noreferrer"><b>here</b></a> on how Haussler's result implies Theorem 2.
<p>
In particular, by Theorem 1, <span class="math-container">$\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$</span> holds over any field. (Interesting is here only the case of <i>infinite</i> fields: for finite ones, much simpler arguments work: Chernoff bound then does the work.) But what about (infinite) semirings that are <i>not</i> fields, or even not rings? Motivated by dynamic programming, I am mainly interested in tropical <span class="math-container">$(\max,+)$</span> and <span class="math-container">$(\min,+)$</span> semirings, but other "non-field" (infinite) semirings are interesting as well.
Note that, over the <span class="math-container">$(\max,+)$</span> semiring, a polynomial 
<span class="math-container">$f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$</span> with 
<span class="math-container">$A\subseteq\mathbb{N}$</span> and <span class="math-container">$c_a\in \mathbb{R}$</span>, turns into the maximization problem 
<span class="math-container">$f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$</span>;
the degree of <span class="math-container">$f$</span> is (as customary) the maximum of <span class="math-container">$a_1+\cdots+a_n$</span> over all <span class="math-container">$a\in A$</span>.
<blockquote>
<b>Question :</b> Is the VC dimension of degree <span class="math-container">$\leq d$</span> polynomials over tropical semirings polynomial in <span class="math-container">$n\log d$</span>?
</blockquote>
 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.
<p>
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)? 
<p>
<b>Proof of Theorem 1:</b>
Assume that a sequence <span class="math-container">$(f_1,\ldots,f_m)$</span> has <span class="math-container">$p$</span> different zero-patterns, and let <span class="math-container">$v_1,\ldots,v_p\in R^n$</span> be witnesses to these zero-patterns. Let <span class="math-container">$S_i=\{k\colon f_k(v_i)\neq 0\}$</span> be a zero-pattern witnessed by the <span class="math-container">$i$</span>-th vector <span class="math-container">$v_i$</span>,  and consider the polynomials <span class="math-container">$g_i:=\prod_{k\in S_i}f_k$</span>.
We claim that these polynomials are
linearly independent over our field. This claim completes the proof of the theorem since each <span class="math-container">$g_i$</span> has degree at most <span class="math-container">$D:=md$</span>, and the dimension of the space of polynomials of degree at most <span class="math-container">$D$</span> is <span class="math-container">$\binom{n+D}{D}$</span>.
To prove the claim, it is enough to note that <span class="math-container">$g_i(v_j)\neq 0$</span> if and only if <span class="math-container">$S_i\subseteq S_j$</span>. Suppose contrariwise that a nontrivial linear relation
<span class="math-container">$\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$</span> exists. Let <span class="math-container">$j$</span> be a subscript
such that <span class="math-container">$|S_j|$</span> is minimal among the <span class="math-container">$S_i$</span> with <span class="math-container">$\lambda_i\neq 0$</span>.
Substitute <span class="math-container">$v_j$</span> in the relation. While <span class="math-container">$\lambda_jg_j(v_j)\neq 0$</span>, we have
<span class="math-container">$\lambda_ig_i(v_j)=0$</span> for all <span class="math-container">$i\neq j$</span>, a contradiction.
<span class="math-container">$\Box$</span>

<co.combinatorics><circuit-complexity><algebraic-complexity><arithmetic-circuits><vc-dimension>
VC dimension of polynomials over tropical semirings?
Stasys
# VC dimension of polynomials over tropical semirings?

(Asked by: username_0 on 2017-03-15)

As in [this](https://cstheory.stackexchange.com/questions/37632/adlemans-theorem-over-infinite-semirings) question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ [problem](https://en.wikipedia.org/wiki/P/poly) 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](http://www.ams.org/journals/proc/1964-015-02/S0002-9939-1964-0161339-9/), [Heintz](http://www.sciencedirect.com/science/article/pii/0304397583900026) and
[Warren](http://www.ams.org/journals/tran/1968-133-01/S0002-9947-1968-0226281-1/);
their proofs use heavy techniques from real algebraic geometry.
In contrast, a half-page proof of Theorem 1 by [Ronyai, Babai and Ganapathy](http://www.ams.org/journals/jams/2001-14-03/S0894-0347-01-00367-8/) (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](http://www.sciencedirect.com/science/article/pii/089054019290010D)) 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**](https://web.vu.lt/mif/s.jukna/ftp/haussler.html) 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$

**Tags:** co.combinatorics, circuit-complexity, algebraic-complexity, arithmetic-circuits, vc-dimension


---

## 1 answers

### Answer by username_0 on 2017-03-24. Score: 9 | Accepted answer

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can be shown using Theorem 1 above. See [here](https://web.vu.lt/mif/s.jukna/ftp/tropical-vc-dim.html)
for details. So, **BPP** $\subseteq$ **P/poly** holds also for tropical circuits and, hence, also for "pure" dynamic programming algorithms.

---

**N.B.** (added 25.06.2019) In the mean time, I've resolved the problem **completely** in [this paper](https://web.vu.lt/mif/s.jukna/ftp/derandDP.pdf). In such a generality, which I haven't even dreamed at the beginning. Tropical case is here just a very, very special case. And even more curiously: by just an appropriate combination of already know (deep in any respect) results of other authors.

What remains else to do in this (BPP vs. P/poly) direction? Besides the decrease of the size of resulting deterministic circuits (an interesting question in itself).


---

