smallest circuit size using XOR gates
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 &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$.

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.