4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ By the way, in a paper with Indyk, Woodruff and Xie (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. $\endgroup$
    – arnab
    Nov 16, 2014 at 5:42

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ “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). $\endgroup$
    – Tsuyoshi Ito
    Nov 16, 2014 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.