Calculating a fast matrix vector product between vector of reals and a 0-1 matrix
Well, if you dont mind some approximation than regular dimension reduction techniques would give you some speedup as they preserve (approximately) dot product.

Otherwise, you can think about each vector as being a CNF clause. If you just have to decide if the dot product is not zero for all vectors, then what you are asking for is the shortest equivalent DNF to the given CNF (or to be more precise some kind of minimal computation that compute the given CNF). This however is easier than the problem of deciding if the given CNF is never satisfiable, which is co-NP complete. In short, this problem should be computationally hard. 

I think there was quite a bit of work on stuff like that in the learning community, especially in the dinosaurs age ;) (80s and earlier?).