Algorithmic Vector Problem

Question

I have an algebraic problem related to vectors in the field GF(2). Let $v_1, v_2, \ldots, v_m$ be (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-vector $u$ of the same dimension such that $u$ is not the sum of any $(\log n)^{O(1)}$ vectors among $v_1,v_2, \ldots, v_m$. The addition of vectors is over the field GF(2), which has two elements 0 and 1 ($0+1=0+1=1$, and $0+0=1+1=0$).

It is easy to see the existence of such a vector u by a simple counting argument. Can we find $u$ in a polynomial time? It is trivial to find $u$ in exponential time. I will send a $200 check award for the first correct solution.

Answer 1

There seems to be a typo; I assume you mean to find $u \in \{0,1\}^n$ which is not the sum of $(\log n)^{O(1)}$ vectors among $v_1,\dots, v_m$ (not $n$).

It's not clear to me if any constant in $(\log n)^{O(1)}$ works for you. If you can settle for sums of less than $\log m$ vectors maybe there's something to be done. But If you want this quantity to be $(\log m)^{1+\delta}$, then I think it is quite hard (I have been working on this problem for a long time).

Still you may be interested to know that this is an instance of the Remote Point Problem of Alon, Panigrahy and Yekhanin ("Deterministic Approximation Algorithms for the Nearest Codeword Problem ") for certain parameters. Let $m > n$ and $v_1,\dots,v_m$ be the columns of the parity check matrix of a linear code in $\{0,1\}^m$ of dimension $d = m - n$ (if this matrix didn't have full rank, the problem would be trivial). Then your problem is equivalent to finding $u \in \{0,1\}^n$ that is $(\log n)^{O(1)}$-far from the code. This setting of parameters, where the dimension is very close to m, is not studied in the paper. However, they can only achive remoteness $\log m$ up to dimension $d = cm$ for some constant $c$. In fact, I don't think we know of any polynomial-sized certificate that allows us to prove that some vector is more than $\omega(\log m)$-far from a space of dimension $\Omega(m)$, let alone find it.

Another connection is with learning parities in the mistake-bound model. If one can efficiently learn $(\log n)^{O(1)}$-parities (defined on ${0,1}^m$) with mistake bound strictly less than $n$, then one can set arbitrary values to the first $n - 1$ bits of $u$ and ``force a mistake'' on the last bit by setting it to the opposite value to that predicted by the learner. This seems much stronger though.

The problem is also related to separating EXP from certain reductions to sparse sets.