XOR function over binary vectors

Question

I didn't really know how to name this question, it has been bothering me for some time:

You are given n binary vectors of dimension $d: x_1,\cdots,x_n$; $x_i = x_{i_1},\cdots,x_{i_d}$.

You are also given n binary values $y_1,\cdots,y_n$.

You need to find some function $f(x)$ which is XOR over some of $x$'s coordinates.

For example: $f(x)= x_1$ XOR $x_3$ XOR $x_8$

Such that for each $i$:

$f(x_i) = y_i$

We assume that there exists such function for the given data.

Thanks!

Answer 1

Solve the linear system $\mathbf A \mathbf c = \mathbf y$ over $\mathbb Z_2$, where the columns of $\mathbf A$ are the given vectors $\mathbf x_i$. The values of $\mathbf c$ will then indicate which $\mathbf x_i$ to include in your function $f$.