Shift-and-or multiplication operation Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold):

Let $r = p \oplus q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication the columns aren't summed up, but rather or'd (not xor) together. Nothing is carried.

$$
  \left[\begin{matrix}
    &amp;&amp;p_n &amp; ... &amp; p_i &amp; ... &amp; p_2 &amp; p_1 \\
    &amp;&amp;q_n &amp; ... &amp; q_i &amp; ... &amp; q_2 &amp; q_1 &amp; \otimes\\
    \hline\\
    &amp;&amp;q_1 \cdot p_n &amp; ... &amp; q_1 \cdot p_i
      &amp; ... &amp; q_1 \cdot p_2 &amp; q_1 \cdot p_1\\
    &amp;q_2 \cdot p_n &amp; ... &amp; q_2 \cdot p_i
      &amp; ... &amp; q_2 \cdot p_2 &amp; q_2 \cdot p_1\\
    &amp;&amp;&amp;&amp;&amp;&amp;&amp;...\\
    q_i \cdot p_n &amp; ... &amp; q_i \cdot p_i
      &amp; ... &amp; q_i \cdot p_2 &amp; q_i \cdot p_1 &amp; \stackrel{i}{\leftarrow}
      &amp;&amp;{\bigvee} \\
    \hline \\
    \\r_{2n}&amp; ... &amp; r_i
      &amp; ... &amp;r_4&amp; r_3 &amp; r_2 &amp;r_1 &amp; =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.
This is equivalent to an operation known as boolean convolution. See Models of Computation page 419 defn 9.6.3.

Dunne states (p5):


  Weiss 1984 and Blum 1984b obtained lower bounds for the n-point boolean convolution function which is closely related to integer multiplication.



Models of computation
Relationships between monotone and non-monotone network complexity, Dunne
Blum, N. (1984b) An $\Omega(n^{4/3})$ lower bound on the monotone network complexity of n-th degree convolution; Theoretical Computer Science, 36, 59-70