1
$\begingroup$

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.

$\endgroup$
3

1 Answer 1

0
$\begingroup$

I believe this is called the low-weight codeword problem. Searching on this will turn up a number of research papers with algorithms for this problem.

$\endgroup$

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