Calculating a fast matrix vector product between vector of reals and a 0-1 matrix Given:
 some vector $R=(r_1...r_l)$ - real numbers,
 and a set of distinct vectors with $0$ or $1$ coordinates
  $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\
  V_2=(c_{2,1} ... c_{2,l}),\\
   .....\\
  V_n=(c_{n,1} ... c_{n,l})\end{array}$$
  each $c_{i,j}$ are $0$ or $1$.
  $n\lt 2^l$ is some number. (For example in my case: $n=2^{10}, l=20$).

 Problem:
I need to calculate inner products $ (R, V_i) $ - how to do this in the fastest way ?
I mean how to organize calculations such that number of additions will be the smallest ?
The point is that some vectors have same subsequences of 1 and 0, 
so I do not need to calculate several times such pieces.

Background: $V_i$ is fixed once and forever, "R" is coming every "millisecond".



Example:
    $V_1 = (1, 1 , 0 , 1)$
    $V_2 = (1, 1 , 1 , 1)$

Algorithm:

x = r_1+r_2+r_4  
y= x+r_3


So $(R, V_1) = x$ ; $(R, V_2) = y$;  required only 3 additions, instead of naively seen $5=2+3$.
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?).