2
$\begingroup$

I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if there exists a subset $Q_k \subset Q$ of at most $k$ vectors ( i.e. $|Q_k| \le k < n$ ) such that $v \in \text{span}\{Q_k\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).

$\endgroup$
1
$\begingroup$

Equivalently, your problem can be stated as:

Given a $m \times n$ matrix $M$ over $\mathbb{F}_2$ and a vector $v \in \mathbb{F}_2^m$, find a vector $x\in \mathbb{F}_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.

There are some hardness results for this problem. For instance, this post argues that the problem can't be approximated within a constant factor, within polynomial time (even for randomized algorithms), assuming standard complexity-theory assumptions.

See also https://cs.stackexchange.com/a/59922/755 and https://cstheory.stackexchange.com/a/10112/5038 and https://cstheory.stackexchange.com/q/27460/5038 and https://cstheory.stackexchange.com/q/10396/5038 for related work, including some algorithmic techniques that might be relevant.

$\endgroup$
  • $\begingroup$ Thank you very much for the comprehensive and insightful answer. I edited it to make the dimensions of the vectors compatible with my original question. $\endgroup$ – Mohsen Kiskani Jan 18 '17 at 0:24

Your Answer

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

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