Minimizing series of XORs Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $m$ initially zero extra temporaries?
I don't know what sort of efficiency you are looking for, it would be good if you clarified it.
Each instruction can be described as a linear map in $\mathbb{F}_2$, so the overall
series of instructions is one linear map.
As for finding the minimal set of instructions, given a limited number of temporary variables, I believe this is analogous to the register allocation problem for compilers, which is NP-COMPLETE.