Boolean convolution algorithm?

Question

I need to perform Boolean convolutions; that is, convolution of bit-vectors where:

• OR is the "addition" operation
• AND is the "multiplication" operation

Is there an algorithm I can use (similar, perhaps, to an FFT) to do this in faster than quadratic time?

I've looked into "number-theoretic transforms" (NTTs), but they seem to be the Fourier analog of modular arithmetic (which wraps around on addition) rather than Boolean arithmetic (which saturates on addition).

The best alternative I'm aware of would be to approximate it via a vector of floating-point 1's and 0's, and simply use an FFT and threshold the result at some cutoff, but this can be error-prone (and potentially slower than necessary, although error is my bigger concern here).
(And in any case, I'd like to know if there's a "correct" way to do this despite this potential alternative.)

Answer 1

If you convolve the Boolean vectors as 0-1 vectors over the integers mod an integer larger than the length of the shorter vector (i.e., the maximum number of terms in a disjunct), then the pattern of nonzero entries is the same.