VNP is closed under taking coefficients using Valiant's criterion

Question

We consider the family of polynomials

$$\{f_n(x_1,\dots,x_n,y_1,\dots,y_n)\}\in\mathsf{VNP}$$

We want to show that the family

$$\{h_n(x_1,\dots,x_n)\}$$

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.

Answer 1

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)$.