Quickly obtaining sums of sets of numbers We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$.  We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For example:

$$s_k = a_3 + a_5 + a_{17} + a_{22} + a_{35}$$

There is more structure to the sums, however.  The sums are split into $m / \alpha$ groups, where each sum is in only one group.  For example, and to make things easier, sums $s_1$, $s_2$,...,$s_{\alpha}$ are in group 1, sums $s_{ \alpha + 1}$,...,$s_{2\alpha}$ are in group 2, and so on.  Then we know that each bit will occur exactly once in each group.

So for example, the bit $a_1$ will appear in each group, the bit $a_2$ will appear once in each group, and so on...

QUESTION

How fast can we calculate all of the sums?

MY IDEAS

If we assume that there are $\alpha$ sums in each group, then there are at most $2^\alpha$ combinations of bits.  For example, if there are two sums, we know that there are four combinations of bits:

(0)  Bits that are not in either sum

(1)  Bits that are in sum 1 ($s_1$), but not in sum 2 ($s_2$)

(2)  Bits that are not in sum 1 ($s_1$), but are in sum 2 ($s_2$)

(3)  Bits that are in both sums.

Thus we need at most $n$ additions to calculate the sums of each of the $m / \alpha$ groups.  So our total time is at most $n(m/\alpha)$ additions, since there are $m/\alpha$ groups.



However, I believe that we can do better!  I'm guessing that we can also use subtraction and sums from different groups to arrive at a much better algorithm.
I believe that we can do even better than this answer, but perhaps this will help.

We split our list of bits $a_1$, $a_2$, $\dots$, $a_n$ into approximately $n / \beta$ collections (these could also be called groups, but I make the distinction so that we know that these are different from the groups above).  Here we set $\beta = \log{(m/(\log{(mn)})}$ In other words, the first collection consists of the first $\beta$ bits $a_1$, $a_2$, $\dots$, $a_{\beta}$.  The second collection consists of the second $\beta$ bits $a_{\beta+1}$, $a_{\beta+2}$, $\dots$, $a_{2\beta}$, and so on.

We find all possible sums for each collection, of which there are approximately $2^{\log{(m/(\log{(mn)}))}} = m/(\log{(mn)})$.  We then calculate each of these sums exactly.  If we're careful, we can calculate each sum in constant time by adding or subtracting one bit from a sum with all other bits the same.

Thus we use roughly $m/(\log{(mn)})$ space to store each solution, times $\log{\log{(mn)}}$ maximum bits per solution, times $n / \log{(mn)}$ different collections.

The running time should be approximately $O \left( \frac{mn \log{ \log{ (mn)}}}{\log{(mn)})^2} \right)$ if I did my calculations right.

This is somewhat faster than the naive approach.  Again, I believe that we can do better.