Suppose that I have $n$ unknown variables $x_1,\ldots,x_n$. I wish to compute their sum: $$Sum(x) = \sum_{i=1}^nx_i$$ However, the only access to these variables is through products: that is, for any subset $S \subset [n]$ I may compute: $$P(S) = \sum_{i prod_{i \in S}x_i$$
That is, I wish to find some number of subsets $S_1,\ldots,S_k$, compute $P(S_1),\ldots,P(S_k)$, and then apply some postprocessing $f$ to find the sum of the variables: $$f(P(S_1),\ldots,P(S_k)) = Sum(x)$$
My question is: How large must $k$ be? Clearly, $k = n$ suffices, since with $k$ subsets I may uniquely identify each $x_i$ and then sum the values myself. Is it possible to do with $k < n$? With $k = O(1)$?
