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.

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

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.