Monotone VP vs monotone VNP

Sources

• Yehudayoff - Separating Monotone VP and VNP
• Notice that I changed the notation a bit for clarity.

Basics

• Computation is over non-negative real numbers.
• MVP is monotone VP and MNVP is monotone VNP.
• Permanent has exponential size monotone circuits.
• Iterated Matrix Multiplication of $d$ matrices needs $n^{\Omega(d)}$ size.

Theorem

• The following polynomial is in MVNP but not in MVP.
• $P_n = 2^{-n} \sum_{b\in {0,1}^n} \prod_{i=1}^n \sum_{j=1}^n b_j x_{i,j}$.
• $P_n$ is obviously in MVNP.

Proof

Definitions

• $X={ x_{i,j} }$.
• We will for a polynomial $f$ and a monomial $m$ write that $m\in f$ if $m$ is a monomial with a non-zero coefficient of $f$.
• We look at monomials of the form $m_I = \prod_{i\in I} x_{i, \phi(i)}$ for an index set $I\subseteq [n]$ and $\phi:[n]\rightarrow [n]$ a partial function.
• We denote by $\alpha_m$ the coefficient of the monomial $m$ or alternatively $\alpha(f,m)$.
• We denote by $\alpha(m,f)$ the coefficient of $m$ in the polynomial $f$.
• We define $I(m_I) = I$ and $f(I(m_I)) = { \phi(i) \mid i\in I(m)}$, i.e., the "from" and "to" indices.
• For a polynomial $f$, $I(f) = \cup_{\text{$m$ is a monomial of $f$}} I(m)$, the union of all index sets of a polynomial.
• We call a polynomial $f$ full if for all $m\in f$, $I(m)=I(f)$. Notice, that this only means that all first indices are hit by every monomial. It does not say anything about the second index of the variables. In essence, we say that $\phi$ is a total function.

Try to redo the polynomial because with f is much better

• $P$ is full.
  • Proof:
  • $P=2^{-n} \sum_{b\in {0,1}^n} \prod_{i=1}^n \sum_{j=1}^n b_j x_{i,j}$
  • This is equal to $P=2^{-n} \sum_{b\in {0,1}^n} \sum_{\phi:[n]\rightarrow [n]} \prod_{i=1}^n b_{\phi(i)} x_{i,\phi(i)}$
    • Notice that the first product basically says: Pick any set multiset of integers of $j$ and build the monomial out of it. The same can be constructed with picking a function $\phi$ from $[n]$ to $[n]$ and construct the monomial directly.
  • ???
  • ????

Lemma 1

• Lemma 1: If $q$ is a full polynomial, we can write $q$ as $\sum_{i=1}^n a_i b_i$ where for all monomials $m$ $0\leq \alpha(a_i,m)\alpha(b_i,m) \leq \alpha(q,m)$ with $n/3\leq \lvert I(a_t)\rvert \leq 2n/3$ and $I(b_t)=[n]\setminus I(a_t)$.
  • We can interprete this lemma as that we have at most a sum of $s$ factorizable polynomials.
  • This means, we can have an order on these monomials and have a roughly even split. Compare this with the multilinear decomposition lemmas.

Proof

• We assume that every gate is computed to the output gate and no gate computes the zero polynomial. As the circuit is monotone, we can easily remove such gates if they occur.
• For each gate $v$ let $a_v$ be the polynomial computed at $v$.
• Monotonicity implies that $a_v$ is full.
  • To see this, divide it into two cases.
  • If we are at an addition $v=v_1+v_2$ gate then every monomial is either in $v_1$ or in $v_2$. By Induction Hypothesis both are full.
  • If we are in the multiplication gate $v= v_1 \cdot v_2$ then by induction hypothesis, $v_1$ and $v_2$ are full, hence their sets $I_{v_1}$, $I_{v_2}$ are given by all monomials.
  • Let us look at the monomial $m_1\in v_1$ and $m_2\in v_2$.
  • Their index set is $I_{v_1}\cup I_{v_2}$. But as every monomial in $v_1$ has $I_{v_1}$ and the same for $v_2$, every monomial has the index set $I_{v_1}\cup I_{v_2}$.
• Now we can go from output to input until we find a vertex $v$ where $n/3\leq \lvert I(v)\rvert \leq 2n/3$ (the order here is not important, so pick any order with respect to the size of $I(v)$).
• Let us look at one such $v$.
• It is part of $q$ in the following way by our index set bound, $q=p_v b_v + r_v$ where $b_v$ is computes at $v$ and non-zero and $r_v$ has a monotone circuit of size at most $s-1$. (Notice that $b_v$ is, of course, non-zero and hence the remainder $r_v$ has to be smaller.)
• By the above inductive argument $p_v$ and $b_v$ is ordered (use $a_v=p_v$ in the lemma).
• Now we can induct on $r_v$ as it has a smaller size.

Measure

• Defining the measure:
  • Let $a,b$ be polynomials with $0\leq \alpha(m,a)\alpha(m,b)\leq \alpha(m,p)$ for all $m$ and $n/3 \leq \lvert I(a)\rvert \leq 2n/3$ and $I(b)=[n]\setminus I(a)$.
  • We can define the measure $\Delta$ as follows:
    • Number of monomials that survive under the projection $\pi$ (divided by $2^n$) where $\pi$ keeps all monomials $m$ such that $\lvert f(I(m))\rvert = k$ with $k = \lfloor \frac{n}{20 + \log n}\rfloor$.

Lemma 2

• Lemma 2: Let $a,b$ be polynomials with $0\leq \alpha(m,a)\alpha(m,b)\leq \alpha(m,p)$ for all $m$ and $n/3 \leq \lvert I(a)\rvert \leq 2n/3$ and $I(b)=[n]\setminus I(a)$. Then $\Delta(ab)\leq \frac{\Delta(P)}{2^{\frac{cn}{\log n}}}$.

Proof

Claim

• Let $\delta = k/n$.
• $1/2(k)^n \leq F_{n,k} \leq k^n$ where $F_{n,k}$ is the number of surjective functions from $[n]$ to $[k]$ and $\delta\leq 1$.
• Proof:
  • The first inequality follows trivially. Every value $k$ can be mapped to at most $n$ many values.
  • For the second: $(\delta n)^n - F_{n,\delta n} \leq \delta n (\delta n - 1)^n$ WHY?
  • $\leq \delta n \left(\delta^n n^n\left(1 - \frac{1}{\delta n}\right)^n\right)\leq \delta^{n+1} n^{n+1} e^{-\frac{n}{\delta n}}$ as $1-x \leq e^{-x}$.
  • By $\frac{1}{\delta}\geq 1+ \log n$: $\delta^{n+1} n^{n+1} e^{-\frac{n}{n} \cdot \left(1 + \log n\right)} = \frac{\delta}{e}\left(\delta n\right)^n$.
  • Hence, the bound holds.

FILL

Theorem

• The proof is now easy.

• We know $\Delta(P)\leq \sum_{t=1}^s \Delta(a_t b_t) \leq s \frac{\Delta(P)}{2^{\frac{cn}{\log n}}}$.

• Hence $\frac{\Delta(P)}{\Delta(P)} \leq \frac{s}{2^{\frac{cn}{\log n}}}$.

• Hence $s\geq 2^{\frac{cn}{\log n}}$.

• Interesting question: Where does this contradict with vp=vnp in multilinear world