# Complexity of extracting a coefficient of a polynomial in multiple variables

I'm looking for efficient algorithms for problems of the following type:

Let's say we have the variables $$x_1,...,x_n$$.

Over these variables, we are given a function $$p_1\cdot ... \cdot p_m$$, consisting of $$m$$ polynomials $$p_1,...,p_m$$, each of which is a multivariate polynomial itself, of the form $$\sum_{\matrix{0\le i_1\le k\\...\\0\le i_n\le k} }a_{i_1,...,i_n} x_1^{i_1}\cdots x_n^{i_n}$$ , where $$k$$ is the highest degree appearing in any of the polynomials $$p_1,...,p_m$$.

How do we efficiently extract a coefficient from $$p_1\cdot ... \cdot p_m$$?

Efficient in this case is relative, as the problem is #P-complete via MacMahon's Master Theorem (it reduces the problem of calculating the permanent to extracting a coefficient of a function as given above).

Nevertheless it's a popular function, implemented in many CAS-systems, and with many applications in e.g. combinatorics.

I'm interested in both efficient algorithms (with complexity bounds) as well as theoretical complexity bounds.

• When you wrote “in #P”, did you actually mean “#P-hard”? – Emil Jeřábek Aug 27 '19 at 7:50
• @EmilJeřábek Yes, that's right, more precisely it's #P-complete – Sudix Aug 30 '19 at 17:01