I have 2 polynomials $p_1(x_1,\ldots,x_n)$ and $p_2(x_1,\ldots,x_n)$, of which I have to compute the product, with a special property: The exponent of each variable is always either $0$ or $1$, where every exponent greater than $1$ gets cut down to $1$. E.g. $x_1 * x_1x_2 = x_1x_2$, and the result of $(2x_1x_2x_4 + 4x_2x_3) * (3x_2x_3 - x_1x_4)$ would be $2x_1x_2x_3x_4 -2x_1x_2x_4 +12x_2x_3$. Additionally, values for all but one variables are given. So the result would be some polynomial $p(x_k) = ax_k + b$.
Currently I compute the product the usual way, multiplying each summand of $p_1$ with every summand in $p_2$, and then apply the values for all known $x_i$. But since both polynomials easily contain $10^5$ summands each, the algorithm iterates over $10^{10}$ elements, which simply takes too much time.
My question is: Does there exists a more effective procedure to compute $p(x_k)$?
Well first of all, if you're making the substitution $x_i^2 = x_i$ for all $i$, then it had better be the case that the only values you are interested in (and so are substituting in) are $x_i = 0$ and $x_i=1$, since these are the only solutions to this equation. So what you're saying is that you're interested in the value of the product $p_1p_2$ as a function of $x_k\in\{0,1\}$ when values in $\{0,1\}$ are substituted in for all the other variables. So just compute $p_1$ and $p_2$ with the given values for indices $i\neq k$ and both values of $x_k$. Multiply the resulting values for the two polynomials when $x_k = 0$ to get the value $p(0)$ and multiply the values for the two polynomials when $x_k =1$ to get the value $p(1)$. Then $b = p(0)$ and $a = p(1) - p(0)$. This will reduce your work from evaluating $10^{10}$ terms to evaluating $4\times 10^5$ terms.