Efficient way of polynomial multiplication with dependency in Bipartite graph form We use a Bipartite graph: $G=(U,V,E)$, with vertices: $U $ and $V$ to represent some task dependency.
Every $U$ is a unique task, and every $V$ is a degree one polynomial, e.g. $(1+v_ix)$.
Our goal is for all the tasks, get their complete polynomial product coefficient.
For $u_1$, the job is to compute $\prod_{(u_1, v_i) \in E} (1+v_ix) = \sum_i g_ix^i$, define $G_1 = (g_0, g_1, \cdots)$ .
And we assume the connection degree of every task node $u$ is bounded by $C$.
Is there any efficient way to obtain all $G_i$ for every $u_i \in U$ ?
 A: "Of course" there is always the idea of treating each task independently. This yields a cost of $\Theta(\sum_i \delta(u_i) \log^2(\delta))$ multiplications of $v_i$, where $\delta$ is the degree. You just do your polynomial expansion for each task. A naïve approach for the multiplications yields a $\Theta(\sum_i \delta(u_i)^2)$, but with fast Fourier transform algorithms you get the said bound. Globally, this cost is $O(n^2 \log^2(n))$. EDIT : It's even $O(|E| \log^2(\delta_{\max})) < O(|E| \log^2(|V|))$.
BUT you could try to find a way to reuse already existing multiplications. Typically, if all the tasks are the same, you could compute only one, and copy it.
This is an interesting idea, but I don't think it's possible to do it in less than $O(m \log^2(n))$ in most cases.
Indeed, even if you had a perfect and instant oracle/algorithm for minimizing the number of multiplications, I guess in most (random) cases I don't think you'll win a significant margin. Unless two tasks have exactly the same dependency set, in the end you'll have to do at least one long multiplication for each task ; and that long multiplication will probably cost you $\delta \log(\delta)$ (apart from marginal cases where you use a polynomial of size about the same as), and at least $\delta$. So, in any case, you couldn't go below a $O(m \log(n))$ for dense graphs, or $O(m)$ if you're very lucky and have a wonderful algorithm.
