Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in the affine $\mathbb R$-span of $\{x_1,\ldots,x_N\}$?
By "efficient" I mean faster than having to test linear independence, i.e., something that exploits the fact that the vectors are binary.