15

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 ]

Community
  • 1
Simd
  • 3,902
  • 20
  • 49
  • (1) If there is a poly-time $2^{n^{1-\epsilon}}$-approximation for any $\epsilon>0$, then there is a poly-time $(1+1/q(n))$-approximation for any polynomial $q$. To see this, given $M$, consider the block-diagonal matrix $M(k)$ formed by $k$ independent copies of $M$ along the diagonal, so $S_M=(S_{M(k)})^{1/k}$. Take $k=(n q(n))^{1/\delta}$. If $x$ is a $2^{(nk)^{1-\epsilon}}$-approximation of $S_{M(k)}$, then $x^{1/k}$ is a $(1+1/q(n))$-approximation of $S(M)$. (2) One has $2^k\le S_M\le 2^n$ where $k$ is the rank of $M$, but this doesn't help as $S_M$ can be large even when $k=m=1$. – Neal Young Jul 30 '18 at 15:36

0 Answers0