<p>This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. <a href="http://link.springer.com/article/10.1007/s00145-012-9124-7">http://link.springer.com/article/10.1007/s00145-012-9124-7</a></p>

<p>The reduction is from Vertex Cover and is very nice. </p>

<p>Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j &lt; n+1$ and $(i,j) \in E$, and $A[i,n+1] = 1$. In other words, given $n+1$ variables $x_1,\ldots,x_{n+1}$ we want to compute the $m$ linear forms $x_i+x_j+x_{n+1}$ for all $(i,j) \in E$.</p>

<p>A little thought shows that there is an XOR circuit for $A$ with gates of fan-in two computing the linear transformation $A$ with only $m+k$ gates, where $k$ is the optimal vertex cover for the graph. (First compute $x_{i'} + x_{n+1}$ for all $i'$ in the vertex cover, using $k$ operations. The linear forms are then all computable in $m$ more operations.) It turns out that this is also a minimum size circuit!</p>

<p>The proof that the reduction is correct is not so nice. I would love to see a short proof that this reduction is correct.</p>

CC BY-SA 3.0
2015-08-13T21:38:41.647Z
Thanks Ryan. Very relevant paper indeed. I thought whether the problem could be as hard as vertex-cover in hypergraphs at least for the case you are not to generate larger XOR sums (what is referred to cancellation-free in this paper I think).
Mohammad R. Salavatipour
CC BY-SA 3.0
2015-08-15T20:54:33.167Z
For the cancellation-free case, the NP-hardness is noted in Garey-Johnson under the somewhat obscure name "Ensemble Computation" (Problem PO9, in A11.1). The reduction is actually same as the one outlined by Ryan, see Section 3.2.2 in G-J.
Janne H. Korhonen
CC BY-SA 3.0
2015-08-13T20:07:35.557Z
2015-08-13T20:07:35.557Z
Ryan Williams
<p>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.</p>

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

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

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

<p>Mohammad Salavatiopur</p>

<circuit-complexity><approximation-hardness><approximation><matrix-product>
smallest circuit size using XOR gates
Mohammad R. Salavatipour
# smallest circuit size using XOR gates

(Asked by: username_0 on 2015-08-13)

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?

Mohammad Salavatiopur

**Tags:** circuit-complexity, approximation-hardness, approximation, matrix-product


---

## 1 answers

### Answer by username_1 on 2015-08-13. Score: 18 | Accepted answer

This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. <http://link.springer.com/article/10.1007/s00145-012-9124-7>

The reduction is from Vertex Cover and is very nice.

Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+1$ and $(i,j) \in E$, and $A[i,n+1] = 1$. In other words, given $n+1$ variables $x\_1,\ldots,x\_{n+1}$ we want to compute the $m$ linear forms $x\_i+x\_j+x\_{n+1}$ for all $(i,j) \in E$.

A little thought shows that there is an XOR circuit for $A$ with gates of fan-in two computing the linear transformation $A$ with only $m+k$ gates, where $k$ is the optimal vertex cover for the graph. (First compute $x\_{i'} + x\_{n+1}$ for all $i'$ in the vertex cover, using $k$ operations. The linear forms are then all computable in $m$ more operations.) It turns out that this is also a minimum size circuit!

The proof that the reduction is correct is not so nice. I would love to see a short proof that this reduction is correct.

> **Comments:**
> **username_0**: Thanks Ryan. Very relevant paper indeed. I thought whether the problem could be as hard as vertex-cover in hypergraphs at least for the case you are not to generate larger XOR sums (what is referred to cancellation-free in this paper I think).  
> **username_2**: For the cancellation-free case, the NP-hardness is noted in Garey-Johnson under the somewhat obscure name "Ensemble Computation" (Problem PO9, in A11.1). The reduction is actually same as the one outlined by Ryan, see Section 3.2.2 in G-J.  

---

