# VNP is closed under taking coefficients using Valiant's criterion

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.

• What do you mean by efficiently computed? Jul 20, 2018 at 15:19
• @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}$. Jul 28, 2018 at 17:03

## 1 Answer

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