How to find the sparsest vector in a given subspace of $\mathbb{F}_2^n$

Question

A subspace $C$ of $\mathbb{F}_2^n$ is given for some $n \geq 1$. The space $C$ is given by its basis.

Is there a polynomial time algorithm to find the (nonzero) vector in $C$ of lowest hamming weight?

Motivation: Finding the distance of a given linear code.

Answer 1

For the purposes of this problem, we restrict ourselves to linear codes presented in terms of its generator (or equivalently, the parity check) matrix. Then Alexander Vardy (1997) showed that computing the minimum distance of a linear code exactly is NP-hard. [The decision version of this problem is: given a linear code $C$ and a bound $k$, does there exist a nonzero codeword $c$ in $C$ of weight $k$ or less? This version is NP-complete.]

There have been several improvements to this basic result -- it's now known that it's also quite hard to (a.) approximate the distance, (b.) decode a received word under the promise that there is a unique codeword close to it, etc. Unfortunately, I don't quite have the time right now to detail all the known developments, but this seems to be a good place to start: http://cseweb.ucsd.edu/~daniele/Research/CodeComp.html . I will try to expand this answer later.

Reference:

A. Vardy, The Intractability of Computing the Minimum Distance of a Code - IEEE Transactions on Information Theory, 1997.