Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?

Question

Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}). Where number of variables is bigger than equations - so we have many solutions $x$.

Question How to estimate minimal Hamming weight of $x$ ($x\ne 0$) ? (I.e. minimal number of $1$ in vector $x$ such that Ax=0).

Equivalently

Consider bipartite graph of vertexes of two type 1 and 2. How to estimate minimal size of subset A of vertexes of type 1, such that: for each vertex $V$ of type 2 we have EVEN number of edges which starts at $V$ and finishes at $A$.

Equivalence can be seen like this: take matrix $A$ of size $n\times m$ over $F_2$ and bipartite graph of with $n$ and $m$ number of vertexes of types 1 and 2. Connect two vertexes if $A_{ij}=1$.

Exercise to see equivalence.

Equivalently

Take $A$ as parity check of linear block code. I.e. code is exactly subspace x: Ax=0. Code is good than Hamming distance between codewords is big. We have code word x = 0, so the minimal Hamming weight of non-zero x will measure the "quality" of code.

Comment. Let Let dim(ker(A))=k, any linear map $F_2^k \to ker(A)$ is called "encoder".

---

[EDIT] As "quid" answered - questions are NP - problems. So

a) what approximate algorithms are used for questions ?

b) If corresponding bipartite graph is tree - is the problem still NP ? (From coding theory it is very simple-degenerate case and bad codes). More generally can we control complexity somehow - if matrix is of special form (e.g. sparse or whatever) or graph is tree/treelike. In what terms we might hope to control complexity ?

[END EDIT]

---

Answer 1

It is known that to determine the minimal weight of a nonzero code word (i.e., the minimum distance of the code) is a hard problem.

Here is a part of the abstract of a paper by Vardy (The intractability of computing the minimum distance of a code, IEEE Information Theory, 1997):

It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978).

However, you ask for an estimation not the exact value. Now, of course it depends what precisely this should mean. Yet, in certain senses the problem stays hard. From the abstract of a paper by Dumer, Micciancio, Sudan (Hardness of Approximating the Minimum Distance of a Linear Code)

We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless NP (nondeterministic polynomial time) equals RP.

In addition, on Sudan's webapage there are slides from a talk on this, see http://people.csail.mit.edu/madhu/talks.html and towards the very end you find 'Hardness of approximating the minimum distance of a linear code'.

ps. I am not certain that this type of answer is what you were looking for, but since your question is not very specific I had to guess a bit.

Answer 2

Seeing as you mentioned the connection to bipartite graphs I think you might be interested in low density parity check (LDPC) codes.

One perspective on this is that minimum distance isn't that big a deal for LDPC codes. The fact that you are using an iterative message passing decoder means that the structure of the graph (girth + more complicated configurations: stopping sets/trapping sets/pseudocodewords) is more important for estimating the performance of the code under belief propagation decoding. Having a few codewords of small weight might not be a problem whereas having many structures that aren't codewords but that confuse your decoder will be.

Still, if you are designing a code you might like to not have small minimum distance. A google search for "estimating minimum distance of ldpc code" brings up a number of likely looking results.

One idea due to Xiao-Yu Hu that comes with software and a paper is on Mackay's webpage (scroll down to "Source code for approximating the MinDist problem of LDPC codes"). This uses the "approximately-nearest-codewords search" where the zero codeword has errors added and is then decoded using belief propagation. This hopefully will sometimes decode to codewords which are close to the zero codeword thus giving you an upper bound on the minimum distance.