The Weight Distribution / Subspace Weights Problem in coding theory is defined as this:
Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$
Question: Is there a set of $k$ columns of $H$ that sum to the all-zero vector?
You might also say:
Given a binary $m$ by$n$ matrix $H$ and an integer $k > 0$, is there a vector $\vec{x}$, s.t.
$$
A\vec{x} = \vec{0}
$$
where $\vec{x}$ has Hamming Weight k?
This Problem is proven to be NP-complete (On the Inherent Intractability of Certain Codiig Problems). But is there any fast (polynomial) exact (for small inputs) or approximation algorithm to solve the problem?
So far I wasn't able to find one.