4

In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.

Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to $y$?

In the answers, comments, and referenced papers I noted

  1. The decision problem is in P.
  2. The natural minimization problem (finding the smallest subset) is NP-hard.
  3. It's related to the problem of finding sparse codewords in a linear code.

My question is: are there any known polynomial-time approximation algorithms for the minimization problem in (2)? I know very little about coding theory, so there may be some obvious or well-known approximation-preserving reductions to (3) that I have not seen.

Community
  • 1
Jeremy Kun
  • 1,318
  • 7
  • 16
  • 1
    By the way, in a paper with Indyk, Woodruff and Xie (http://drona.csa.iisc.ernet.in/~arnabb/boolcycles.pdf), we showed that the problem of finding whether there are $k$ $v_i$'s that sum to $y$ requires at least $\min(n^{\Omega(k)}, 2^{\Omega(d)})$ time assuming ETH, if $v_1, \dots, v_n$ are $n$ vectors of dimension $d$. This bound is also tight. – arnab Nov 16 '14 at 05:42

1 Answers1

3

Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum distance problem is the same as your problem if the $v_i$'s form the columns of the parity check matrix and $y = 0$.

arnab
  • 7,000
  • 1
  • 38
  • 55
  • 3
    “The minimum distance problem is the same as your problem if the v_i's form the columns of the parity check matrix and y=0.” As is stated, this is not true. The special case of the problem in question with y=0 is easy to solve: the zero vector is always the optional solution. The minimum distance problem is equivalent to finding the solution with the second smallest weight. I think that you need a slightly more delicate randomized reduction (by adding one constraint $c^T x=1$ with a randomized chosen vector c). – Tsuyoshi Ito Nov 16 '14 at 19:17