Author here.
The idea is a mix of many things. This is not how we write it in the paper, but just for intuition.
If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then
Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n).
Here A+B = {a+b|a in A, b in B}
+ is associative and commutative. Now we want to add parenthesis on that formula in a way such that it is fast. Similar to matrix chain multiplication. We make sure + can be fast if certain property are satisfied(Theorem 2), and the rest is just figuring out the right way to add parenthesis.
chaoxu|10 years ago
If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then
Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n).
Here A+B = {a+b|a in A, b in B} + is associative and commutative. Now we want to add parenthesis on that formula in a way such that it is fast. Similar to matrix chain multiplication. We make sure + can be fast if certain property are satisfied(Theorem 2), and the rest is just figuring out the right way to add parenthesis.