# 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?

• Do you mean that in the end all values of $x_i$ must be the same as after the original set of instructions? I mean, if we want only one value in the end, it'll make the problem trivial (just count the parity of inputs in the final expression). – Dmitry Jul 29 '20 at 11:34
• @Dmitry The set of instructions when executed can be seen as a function $f : \{0,1\}^n \to \{0,1\}^n$. Can we efficiently find a smaller set of instructions, forming function $g : \{0,1\}^n \to \{0,1\}^n$ such that $\forall \mathbf{x} (f(\mathbf{x}) = g(\mathbf{x}))$? That is my question, with the addition of allowing some temporary variables for $g$ as well (which are initially zero and ignored for the output). Note that sometimes even without temporaries you can already do better. – orlp Jul 29 '20 at 12:49
• Each instruction can be described as a linear map in $\mathbb_2{F}$, so the overall series of instructions is one binary matrix, with AND and XOR as multiplication and addition respectively. Is this efficient enough? – Richie Yeung Jul 29 '20 at 12:57
• Your type of program is known as a "linear circuit", see e.g. www3.nd.edu/~jhauenst/preprints/ghilRigidity.pdf. One usually allows more complicated instructions (XOR of several arguments), but the complexity measure is the total number of operands ("edges"). I expect minimizing such circuits to be hard. In your case you also have a bound on the memory; I'm not sure this has been considered in this context (but does appear in related computation models such as branching programs, as the "width" of the program). – Yuval Filmus Jul 29 '20 at 13:30
• @YuvalFilmus I guess this proof also applies, for sufficiently large $m$? cstheory.stackexchange.com/questions/32267/… – orlp Jul 29 '20 at 13:38

Each instruction can be described as a linear map in $$\mathbb{F}_2$$, so the overall series of instructions is one linear map.