Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted $|B|=\sum_{b\in B}|b|$, where $|b|$ is the Hamming weight of vector $b\in\mathbb{F}_2^m$. Out of all bases for $V$, some bases have the minimum weight. We call these the minimum bases for $V$.

In general, finding a minimum basis is NP-hard, because it would allow one to calculate the distance of the binary, linear code with codespace $V$. However, given some sparsity constraints on $A$, the problem of finding a minimum basis for $V$ can be easy.

For example, if each row of $A$ has exactly two non-zero entries (two 1s), then a minimum basis for $V$ can be produced in $\text{poly}(m,n)$ time. This is because $A$ can then be interpreted as the incidence matrix for a graph $G$ with $m$ edges and $n$ vertices. Then, the minimum basis problem is equivalent to finding a minimum cycle basis for $G$, a task that can be performed by e.g. Horton's algorithm.

This brings me to my main question. Can anything be said about the time complexity of finding a minimum basis for $V$ when each row of $A$ has exactly three non-zero entries?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.