Finding coefficient of multivariate polynomial $f(x_1,x_2,\ldots x_n)$ is polynomial with integer coefficients.
$f$ is rather large to be computed explicitly, but an algorithm can
compute it efficiently at integers and complex number and "lazy" form using
parenthesis.
The degree of $f$ is $n$.
Let $C$ be the coefficient of the monomial $\prod_{i=1}^n x_i$.

Q1: What is the complexity of deciding if $C$ is zero or not?
Q2: What is the complexity of computing $C$?

Can we do better than $\exp(o(n())$ (small oh)?
Possible approaches:

*

*Find some domain $K$ with many nilpotent elements
and work over $K[x_1,x_2,\ldots x_n]/(x_1^2,x_2^2 \ldots x_n^2)$

*Using Automatic differentiation compute the partial derivative.

 A: Since the degree of $f$ is $n$, the monomial $x_1x_2\dots x_n$ is the only one containing every variable. Then by inclusion-exclusion, we have
$$C = \sum_{v\in\{0,1\}^n} (-1)^{n-s(v)} f(v),$$
where $s(v):=\sum_{i=1}^n v_i$.
A: I think these comments may be helpful.
I will assume that we have some polynomial or multinomial (perhaps with monomials from some restricted set) and an oracle which instantly returns the value at any given point (perhaps from a restricted domain). We wish to find a specific coefficient and wonder how many queries we need to make and how hard the calculation would be. Each query gives a  linear combination of the various coefficients so we wonder how small a system of equations (drawn from the restricted class available to us) suffices. I would expect that in general (but not always) $m$ queries would be required where $m$ is the potential number of monomials. So it (often) takes as many queries to get one particular coefficient as to get them all.
Consider first this problem: Given a polynomial $\sum_0^na_nx^n$ find $a_i.$ Then $a_0=f(0).$ But it would take $n+1$ queries to specify any other coefficient or even to find $a_0$ if we were not allowed to ask about $f(0).$ At that point we could find them all. If we had an upper bound  $\max_i(|a_i|)\lt B$ and wanted $a_n$ then  $|a_n-\frac{f(N)}{N^n}| \lt \varepsilon$ for $N \gt \frac{nB}{\varepsilon}.$ If the coefficients were know to be integers this might be effective.This isn't the given problem so I will not discuss finding $f(e^{2j\pi/n}),$ precomputing the inverse of a Vandermonde matrix or doing successive differences.
Next suppose that we know in advance that the vector of variables is $\mathbf{x}=(x_1,\cdots,x_n)$ and $f(\mathbf{x})=\sum_Sa_S\prod_{i \in S}x_i$ where $S$ varies over the subsets of $[n]=\{1,\cdots ,n\}.$ Then there are $2^n$ coefficients. If our queries need are restricted to $0-1$ vectors then to find $a_S$ would could do $2^{|S|}$ queries (setting all irrelevant variable to $0$) and use inclusion exclusion. If done correctly we could have all $a_T$ for $T \subseteq S$ for the same work. This would seem best possible.
Minimality Suppose I tell you in advance that $f=\prod_1^n z_i$ where either $z_i=x_i$ or $z_i=1-x_i.$ Then  the coefficient of $x_1x_2\cdots x_n$ is $\pm 1$ and we wish to determine which it is. Then each of the $2^n$ possible queries will return $0$ except a particular one which will tell us everything. If we are lucky we find out in a few queries, but it could take $2^n$ queries. 
In this rather restricted case one can technically do it with one evaluation: Set $$x_i=\frac{2^{2^i}}{1+2^{2^i}}.$$ 
Then the result is a fraction with an odd denominator and numerator $2^{2^k}$ where the bits of $k$ tell us which $z_i=x_i.$
The question as asked concerns linear combinations of monomials in $n$ variables all of degree at most $n.$ There are $\binom{n+k-1}k$ such monomials of degree $k$ so potentially $\binom{2n}n \approx \frac{4^n}{\sqrt{\pi n}}$ summands. In this case, for each $T \subseteq [n]$, $2^{|T|}$ queries suffice to determine  the sum of all the coefficients for monomials using positive powers of exactly $\{x_t \mid t \in T\}.$ For $T=[n]$ this sum is, as remarked above, just what we want.
I suspect that if we can't use $0-1$ vectors , for example all the $x_i$ in a query need to be integers at least $2$, then $2^n$ queries would not be enough. Maybe then it would take $\binom{2n}n$ queries.

Here is an interesting case I wondered about. Suppose we explicitly see that $$f=\prod_{i=1}^n\left(\sum_{j=1}^na_{ij}x_j+c_i\right).$$ Then the finding the coefficient in question amounts to computing the permanent of the matrix $A={\huge(}a_{ij}{\huge)}.$ Naively that takes $n!n$ operations. This can perhaps be sped up to $2^nn^2$ or $2^nn.$ Much more than for the determinant. Of course each of our allowed queries instantly gives us the result of many arithmetic operations so it is not contradictory that $2^n$ suffice.
For that matter, we don’t need the information about where $f$ came from. I was just emphasizing that knowing that was no real help. The method here merely uses that $f$ is some linear combination of $\binom{2n}{n}$ monomials.
