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\}|.$$I believe that it is NP-hard to compute $S_M$ exactly, by applying the reductions from Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1 to the following decision problem: does $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?[Cross-posted to https://mathoverflow.net/questions/229852/complexity-of-approximating-the-size-of-the-range-of-a-matrix ] 
Complexity of approximating the range of a matrix
cc.complexity theory;approximation algorithms;linear algebra