<p>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$).</p>

<p>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). </p>

<p>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 &gt; 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 <em>prove</em> that some vector is more than $\omega(\log m)$-far from a space of dimension $\Omega(m)$, let alone find it.</p>

<p>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.</p>

<p>The problem is also related to separating EXP from certain reductions to sparse sets.</p>

CC BY-SA 3.0
2012-02-22T16:19:01.000Z
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
CC BY-SA 3.0
2012-02-22T11:17:05.907Z
2012-02-22T11:17:05.907Z
david
<p>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$).</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-21T22:12:42.283Z
it seems vaguely related to the subset sum problem which is NP complete. however that uses full integer sum instead of XOR.
vzn
CC BY-SA 3.0
2012-02-21T22:28:54.963Z
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
CC BY-SA 3.0
2012-02-21T23:31:55.673Z
how about super-poly algorithms, i.e., m^log(n) ?
Dimitris
CC BY-SA 3.0
2012-02-21T23:50:24.200Z
@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
CC BY-SA 3.0
2012-02-22T00:29:02.393Z
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
CC BY-SA 3.0
2012-02-22T15:39:22.537Z
@NieldeBeaudrap No, the problem you state is different (although it's still hard). I don't know why you think that your problem being in NP would imply an algorithm to find $u$.
david
CC BY-SA 3.0
2012-02-22T16:16:09.643Z
Even an O(n^{log n}) time deterministic algorithm for this problem would be very interesting.  A random vector u has a high probability to satisfy the requirement, but it is unknown how to verify it in a polynomial time.
Bin Fu
CC BY-SA 3.0
2012-02-22T17:40:29.720Z
@david: I'm not saying that this problem is the same, exactly: but because suitable vectors **u** should be extremely common (by the same counting argument hinted at by the OP), randomly guessing a vector **u** followed by checking whether it works should be sufficient, with very few repetitions. Do you disagree?
Niel de Beaudrap
CC BY-SA 3.0
2012-02-22T19:43:04.073Z
@NieldeBeaudrap I agree that what you describe would give a randomized algorithm (although not a deterministic one), but I don't see that has anything to do with being in NP. Also the "checking" you need is probably a much harder problem.
david
CC BY-SA 3.0
2012-02-23T03:34:54.247Z
Ok here is a very simple quazi-poly algorithm. Let $m=n^r$ and $\log^{O(1)}(n)=\log^t(n)$, for simplicity. Then, for each of the $S={{m}\choose{\log^t(n)}}=O\left(m^{\log^t(n)}\right)$ subsets of $\log^t(n)$ vectors generate their XOR. Now you have a list of $S$ binary vectors. Find a vector in their nullspace (poly in $S$), i.e. total complexity poly(N), quazi-poly in $m$. If you want to avoid the nullspace calculation you could transform all $S$ vectors in integers, then sort them, then pick one that is not in that list, and then transform this number back to a vector. Again quazi-poly time.
Dimitris
CC BY-SA 3.0
2012-02-23T03:38:10.577Z
The random approach is to verify the randomly drawn vector by checking the $S$ XOR vectors, again in quazi-poly time.
Dimitris
CC BY-SA 3.0
2012-02-23T09:19:34.677Z
A reformulation, I do not know if this can help. If $v=(v_1,\dots,v_n)$, let $\bar x^v=x_1^{v_1}x_2^{v_2}\dots x_n^{v_n}$. Then, $v+v'$  corresponds to $\bar x^v\bar x^{v'}\mod\langle x_1^2-1,\dots,x_n^2-1\rangle$. Consider now the $m$ vectors $v_1$, ..., $v_m$, and the corresponding monomials $\bar x^{v_1},\dots,\bar x^{v_m}$. Let $p(\bar x)=\sum_i\bar x^{v_i}$. Then, you are looking for a monomial which does not appear in $p(\bar x)^{\log^{\mathcal O(1)} n}\mod\langle x_i^2-1\rangle$.
Bruno
<ds.algorithms><linear-algebra>
Algorithmic Vector Problem
Bin Fu
# Algorithmic Vector Problem

(Asked by: username_0 on 2012-02-21)

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.

**Tags:** ds.algorithms, linear-algebra

> **Comments:**
> **username_1**: it seems vaguely related to the subset sum problem which is NP complete. however that uses full integer sum instead of XOR.  
> **username_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.  
> **username_2**: how about super-poly algorithms, i.e., m^log(n) ?  
> **username_2**: @username_3: 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?  
> **username_3**: To extend username_1'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**.  
> **username_4**: @NieldeBeaudrap No, the problem you state is different (although it's still hard). I don't know why you think that your problem being in NP would imply an algorithm to find $u$.  
> **username_0**: Even an O(n^{log n}) time deterministic algorithm for this problem would be very interesting.  A random vector u has a high probability to satisfy the requirement, but it is unknown how to verify it in a polynomial time.  
> **username_3**: @username_4: I'm not saying that this problem is the same, exactly: but because suitable vectors **u** should be extremely common (by the same counting argument hinted at by the OP), randomly guessing a vector **u** followed by checking whether it works should be sufficient, with very few repetitions. Do you disagree?  
> **username_4**: @NieldeBeaudrap I agree that what you describe would give a randomized algorithm (although not a deterministic one), but I don't see that has anything to do with being in NP. Also the "checking" you need is probably a much harder problem.  
> **username_2**: Ok here is a very simple quazi-poly algorithm. Let $m=n^r$ and $\log^{O(1)}(n)=\log^t(n)$, for simplicity. Then, for each of the $S={{m}\choose{\log^t(n)}}=O\left(m^{\log^t(n)}\right)$ subsets of $\log^t(n)$ vectors generate their XOR. Now you have a list of $S$ binary vectors. Find a vector in their nullspace (poly in $S$), i.e. total complexity poly(N), quazi-poly in $m$. If you want to avoid the nullspace calculation you could transform all $S$ vectors in integers, then sort them, then pick one that is not in that list, and then transform this number back to a vector. Again quazi-poly time.  
> **username_2**: The random approach is to verify the randomly drawn vector by checking the $S$ XOR vectors, again in quazi-poly time.  
> **username_5**: A reformulation, I do not know if this can help. If $v=(v_1,\dots,v_n)$, let $\bar x^v=x_1^{v_1}x_2^{v_2}\dots x_n^{v_n}$. Then, $v+v'$  corresponds to $\bar x^v\bar x^{v'}\mod\langle x_1^2-1,\dots,x_n^2-1\rangle$. Consider now the $m$ vectors $v_1$, ..., $v_m$, and the corresponding monomials $\bar x^{v_1},\dots,\bar x^{v_m}$. Let $p(\bar x)=\sum_i\bar x^{v_i}$. Then, you are looking for a monomial which does not appear in $p(\bar x)^{\log^{\mathcal O(1)} n}\mod\langle x_i^2-1\rangle$.  

---

## 1 answers

### Answer by username_4 on 2012-02-22. Score: 8

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.

> **Comments:**
> **username_0**: 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  

---

