Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$
It is NP-hard to compute $S_M$ exactly I believe by applying the reductions from this cstheory question and answer to the following decision problem. Is $S_M < 2^n$?
Is it possible to approximate $S_M$ to within a constant factor in polynomial time? If not, what is the best one can do in polynomial time?
My hunch is that a constant factor approximation cannot be achieved in polynomial time (unless P = NP maybe under some complexity theoretic assumption) but it would be very interesting to know how to give even a square root approximation, for example.
[Previously asked at https://cstheory.stackexchange.com/questions/33676/complexity-of-approximating-the-range-of-a-matrix with no answers/comments.]