We consider the family of polynomials


We want to show that the family


is in $\mathsf{VNP}$. Where $h_n(x_1,\dots,x_n)=[\text{coefficient of } y_1\cdots y_n \text{ in } f_n]$.

From Valiant's criterion it is enough to show that given any vector of exponents $$e=(e_1,\cdots,e_n)$$ we can efficiently (in $\mathsf{\# P/Poly}$) compute the coefficient of the monomial $x_1^{e_1}\cdots x_n^{e_n}$ in $h_n$. But this is exactly the coefficient of the monomial $x_1^{e_1}\cdots x_n^{e_n}y_1\cdots y_n$ in $f_n$.

I now want to say that it can be efficiently computed since $\{f_n\}\in\mathsf{VNP}$, but I feel it is the other direction of Valiant's criterion which we cannot use.

  • $\begingroup$ What do you mean by efficiently computed? $\endgroup$
    – Turbo
    Jul 20 '18 at 15:19
  • $\begingroup$ @Problem What I mean by that is to compute it in $\mathsf{\# P/Poly}$, as I said. If we show that, then by Valiant's criterion we are done since the criterion says that $h_n\in\mathsf{VNP}$. $\endgroup$
    – user554578
    Jul 28 '18 at 17:03

Here is a related statement which can be proven "algebraically" (as opposed to going to the boolean world of #P/poly).

Suppose $f(x_1,\ldots,x_n,y_1,\ldots,y_m) \in \text{VNP}$ for $m = \text{poly}(n)$. Then for any $e_1,\ldots,e_m$, the "coefficient" of $y_1^{e_1}y_2^{e_2} \cdots y_m^{e_m}$ in $f$ (a polynomial in $x_1,\ldots,x_n$) is also in $\text{VNP}$.

Proof sketch: We will prove the statement for $m=1$, the main statement would then follow.

Suppose the degree of $y$ in $f$ is strictly less than $D = 2^d$, for some integer $d$ (pick the smallest one). Note that for any polynomial $g(y)$ of degree $< D$, and any $0 \leq e_1 < D$, we have that for every choice of distinct constants $a_0, a_1, \ldots, a_{D-1}$, there exists constants $\beta_0,\ldots,\beta_{D-1}$ (independent of $g$) such that the coefficient of $y^e$ in $g(y)$ is given by $\sum_{0 \leq i \leq D-1} \beta_i g(a_i)$. This is just univariate interpolation.

Next, note that we can design a polynomial $c_e(a)$ of degree at most $D$, such that $c_e(a_i) = \beta_i$ for each $i$.

Now, here is a "$\text{VNP}$-expression" for the coefficient of $y^e$ in $f(x_1,\ldots,x_n,y)$. $$ \sum_{i_1,\ldots,i_d \in \{0,1\}} c_e(val(i_1,\ldots,i_d)) f(x_1,\ldots,x_n,val(i_1,\ldots,i_d)),$$ where $val(i_1,\ldots,i_d) = \sum_{1 \leq j \leq d} 2^{j-1} i_j $, the value of the binary number given by the $i$'s.

Repeatedly applying the above argument, we get that the number of auxiliary variables that we need for an arbitrary coefficient is at most $m \cdot \log D = O(m \cdot \log(\text{deg}(f))) = \text{poly}(n)$.


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.