2

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.)

Improve this question
7
  • 1
    Are you sure you want to use OR for "addition" ? Normally, AND and XOR give you a ring structure on the Booleans... Commented Mar 27, 2014 at 9:40
  • note: I see some optimization opportunities: 1) if you use OR, you can short circuit. 2) you can keep a count of 0s/1s in the window (or both windows) and when it's all 0s/1s, you know the result for that discrete point. Commented Mar 27, 2014 at 9:42
  • @Krystian: Yeah; I'm not looking for a ring structure here. So that means convolve([1], [1]) should most certainly be [1] for my application. Commented Mar 27, 2014 at 9:53
  • @KarolyHorvath: I'm not sure what you mean. Are you thinking of run-length encoding? If you are, I think that while it's pretty efficient in some cases, it can be quadratic in other cases. If not, then I don't think I understood what you meant. Commented Mar 27, 2014 at 9:54
  • 1) as you said, addition saturates. once it reaches 1, it's going to stay there, so there's no need to calculate the rest of the operations for this value Commented Mar 27, 2014 at 10:19

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

+1 it did occur to me at some point, but I didn't realize it has to be the length of the shorter vector. Thanks for pointing it out. (Still looking for a better answer, but at least this gives an exact solution.)
@Mehrdad Re a better answer: there are semirings where we don't know how to convolve efficiently (see, e.g., mathoverflow.net/questions/10237/…). If a better algorithm is known, then it exploits the structure of the Boolean semiring in some fundamentally different way. This would be a pretty interesting result, so I feel as though I would have encountered it by now if it existed (but then again this is not my "home" subfield of algorithms). You could try the cstheory site.
Oh wow, that's really interesting. The reason I thought it might be possible is that when I searched, I saw "FFT" mentioned everywhere, but I wasn't sure how it would apply to Boolean convolution. For example, on this page, they mention "Boolean Convolutions (FFT)" but don't mention how to do it, so I wasn't sure what to do there. I might try that site, thanks..

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.