<p>Here is a related statement which can be proven &quot;algebraically&quot; (as opposed to going to the boolean world of #P/poly).</p>
<p>Suppose <span class="math-container">$f(x_1,\ldots,x_n,y_1,\ldots,y_m) \in \text{VNP}$</span> for <span class="math-container">$m = \text{poly}(n)$</span>. Then for any <span class="math-container">$e_1,\ldots,e_m$</span>, the &quot;coefficient&quot; of <span class="math-container">$y_1^{e_1}y_2^{e_2} \cdots y_m^{e_m}$</span> in <span class="math-container">$f$</span> (a polynomial in <span class="math-container">$x_1,\ldots,x_n$</span>) is also in <span class="math-container">$\text{VNP}$</span>.</p>
<p><em>Proof sketch</em>: We will prove the statement for <span class="math-container">$m=1$</span>, the main statement would then follow.</p>
<p>Suppose the degree of <span class="math-container">$y$</span> in <span class="math-container">$f$</span> is <em>strictly less than</em> <span class="math-container">$D = 2^d$</span>, for some integer <span class="math-container">$d$</span> (pick the smallest one).
Note that for any polynomial <span class="math-container">$g(y)$</span> of degree <span class="math-container">$&lt; D$</span>, and any <span class="math-container">$0 \leq e_1 &lt; D$</span>, we have that for every choice of distinct constants <span class="math-container">$a_0, a_1, \ldots, a_{D-1}$</span>, there exists constants <span class="math-container">$\beta_0,\ldots,\beta_{D-1}$</span> (independent of <span class="math-container">$g$</span>) such that the coefficient of <span class="math-container">$y^e$</span> in <span class="math-container">$g(y)$</span> is given by <span class="math-container">$\sum_{0 \leq i \leq D-1} \beta_i g(a_i)$</span>. This is just univariate interpolation.</p>
<p>Next, note that we can design a polynomial <span class="math-container">$c_e(a)$</span> of degree at most <span class="math-container">$D$</span>, such that <span class="math-container">$c_e(a_i) = \beta_i$</span> for each <span class="math-container">$i$</span>.</p>
<p>Now, here is a &quot;<span class="math-container">$\text{VNP}$</span>-expression&quot; for the coefficient of <span class="math-container">$y^e$</span> in <span class="math-container">$f(x_1,\ldots,x_n,y)$</span>.
<span class="math-container">$$ \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)),$$</span>
where <span class="math-container">$val(i_1,\ldots,i_d) = \sum_{1 \leq j \leq d} 2^{j-1} i_j $</span>, the value of the binary number given by the <span class="math-container">$i$</span>'s.</p>
<p>Repeatedly applying the above argument, we get that the number of auxiliary variables that we need for an <em>arbitrary</em> coefficient is at most <span class="math-container">$m \cdot \log D = O(m \cdot \log(\text{deg}(f))) = \text{poly}(n)$</span>.</p>

CC BY-SA 4.0
2021-08-25T13:38:24.170Z
2021-08-25T13:38:24.170Z
anamay
<p>We consider the family of polynomials</p>

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

<p>We want to show that the family</p>

<p>$$\{h_n(x_1,\dots,x_n)\}$$</p>

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

<p>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$.</p>

<p>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.</p>

CC BY-SA 4.0
2018-07-20T15:19:54.223Z
What do you mean by efficiently computed?
Turbo
CC BY-SA 4.0
2018-07-28T17:03:13.870Z
@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}$.
user554578
<algebraic-complexity><arithmetic-circuits>
VNP is closed under taking coefficients using Valiant's criterion
user554578
# VNP is closed under taking coefficients using Valiant's criterion

(Asked by: username_0 on 2018-06-01)

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.

**Tags:** algebraic-complexity, arithmetic-circuits
> **Comments:**
> **username_1**: What do you mean by efficiently computed?  
> **username_0**: @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}$.  

---

## 1 answers

### Answer by username_2 on 2021-08-25. Score: 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)$.


---

