# Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the number of terms in the polynomial?

What I could come up with:

• As the variables are binary, they all follow the equation X²=X

• You can represent any polynomial of this kind with an array of $$2^n$$ values, where n is the number of variables, where each index represents the variables multiplied and the value at the index position represents the quantity multiplied.

Example: for a polynomial with 3 variables, the array indexes will be as follows:
0 - _
1 - a
2 - b
3 - a * b
4 - c
5 - a * c
6 - b * c
7 - a * b * c

And the polynomial 1+3a-2b+bc could be represented as [1, 3, -2, 0, 0, 0, 1, 0]

• to add two polynomials in this representation you just have to add the arrays

• the value of the multiplication of two terms can be calculated multiplying their values and the index can be found by applying OR in their indexes. Example: array A and array B represents two distinct binary polynomials and K is the result of the multiplication. A[i] * B[j] -> K[i | j] = A[i] * B[j]

So, is there a faster way than looping and distributing each term?

• Your representation requires an array of size $2^n$. It can be much more than the actual number of terms in the polynomial. – Dmitry Mar 27 at 17:26
• @Dmitry you are correct, thanks for pointing that out. It was a typo in the question. And while it can be much more than the actual polynomial, I can't think of a better representation than that for making the calculations – Victor Marcelino Mar 27 at 18:09
• – D.W. Mar 27 at 19:32
• Are your polynomials sparse or dense? How many variables are involved? – Yuval Filmus Mar 28 at 16:21
• The answer could also depend on the representation that you use. For example, if you multiply $x_1 + \cdots + x_n$ by $y_1 + \cdots + y_n$ and you represent polynomials as sums of terms, then you cannot do better than $\Theta(n^2)$, since the resulting polynomial has $n^2$ terms. In fact, it could be worse if each monomial has high degree — your upper bound of $O(n^2)$ doesn't necessarily hold, depending on your model of computation. – Yuval Filmus Mar 28 at 16:23