3 added 482 characters in body

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".

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]

2 ($x\ne 0$

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".

1

# 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 ?

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$ ? (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".