title: Boolean convolution algorithm?
body: <p>I need to perform Boolean convolutions; that is, convolution of bit-vectors where:</p>
  
  <ul>
  <li>OR is the "addition" operation</li>
  <li>AND is the "multiplication" operation</li>
  </ul>
  
  <p>Is there an algorithm I can use (similar, perhaps, to an FFT) to do this in faster than quadratic time?</p>
  
  <p>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).</p>
  
  <p>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).<br>
  (And in any case, I'd like to know if there's a "correct" way to do this despite this potential alternative.)</p>