Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
it seems vaguely related to the subset sum problem which is NP complete. however that uses full integer sum instead of XOR. –  vzn Feb 21 '12 at 22:12
1  
strangely I have recently been trying to formulate & look at a similar problem. try sec13.5 of stasys jukna book on boolean function complexity. it looks like your q can be formulated in terms of linear circuits in that chapter. –  vzn Feb 21 '12 at 22:28
1  
how about super-poly algorithms, i.e., m^log(n) ? –  Dimitris Feb 21 '12 at 23:31
1  
@Niel de Beaudrap: but the number of XORs you have to check is super-poly (i.e., roughly ${{m}\choose{\log(n)}}$), not poly. Isn't that a problem? –  Dimitris Feb 21 '12 at 23:50
1  
To extend vzn's remark: it would seem that nearly any vector satisfies your requirements, by the same counting argument. I imagine that you would also like a proof that a (perhaps randomly generated) vector is not contained in any subspace spanned by polylog(n) of the vectors: so your question is tantamount to showing that the problem of determining whether or not a candidate vector u doesn't belong to a subspace generated by some dimension f(n) ∈ polylog(n) of the vectors $\mathbf v_j$ is in NP. –  Niel de Beaudrap Feb 22 '12 at 0:29
show 7 more comments

1 Answer

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.

share|improve this answer
1  
Thanks for pointing out the typo. The last “v_n” should be “v_m”. Hope someone will fix it. Your answer contains helpful information. +1 –  Bin Fu Feb 22 '12 at 16:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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