<p>Dumer, Miccancio and Sudan <a href="https://cseweb.ucsd.edu/~daniele/papers/DMS.html" rel="nofollow">showed</a> 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$.</p>

CC BY-SA 3.0
2014-11-16T19:17:16.867Z
“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
CC BY-SA 3.0
2014-11-16T05:46:40.580Z
2014-11-16T05:46:40.580Z
arnab
<p>In <a href="https://cstheory.stackexchange.com/questions/10396/0-1-vector-xor-problem">this question</a> vzn asked about the following problem, which I'll call Vector-Subset-Sum.</p>

<blockquote>
  <p>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$?</p>
</blockquote>

<p>In the answers, comments, and referenced papers I noted</p>

<ol>
<li>The decision problem is in P.</li>
<li>The natural minimization problem (finding the smallest subset) is NP-hard.</li>
<li>It's related to the problem of finding sparse codewords in a linear code.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2014-11-16T05:42:30.303Z
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
<approximation-algorithms><optimization><linear-algebra><coding-theory>
Approximation algorithms for min vector subset-sum over GF(2)
Jeremy Kun
# Approximation algorithms for min vector subset-sum over GF(2)

(Asked by: username_0 on 2014-11-15)

In [this question](https://cstheory.stackexchange.com/questions/10396/0-1-vector-xor-problem) 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.

**Tags:** approximation-algorithms, optimization, linear-algebra, coding-theory
> **Comments:**
> **username_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.  

---

## 1 answers

### Answer by username_1 on 2014-11-16. Score: 3

Dumer, Miccancio and Sudan [showed](https://cseweb.ucsd.edu/~daniele/papers/DMS.html) 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$.

> **Comments:**
> **username_2**: “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).  

---

