Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables. The goal is to compute the minimum number of XOR operations you need to perform to compute all these y_1...y_m functions.
Note that the result of an XOR operation, say x_1 XOR x_2 might be used in computation of multiple y_j's but is counted as one. Also, note that it might be useful to compute XOR of a much larger collection of x_i's (larger than any y_i function, e.g. computing XOR of all x_i's) in order to compute y_i's more efficiently,
Equivalently, suppose we have a binary matrix A, and a vector X and the goal is to compute vector Y such that A.X=Y where all operations done in GF(2) using minimum number of operations.
Even when each row of A has exactly k one's (say k=3) is interesting. Does anybody know about the complexity (hardness of approximation) for this question?