6
$\begingroup$

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.

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.