k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable.  Here $\oplus$ denotes the binary [XOR][1] operation, $I$ is some index set, and each clause has $k$ distinct literals $l_{s_{ij}}$ each of which is either a variable $x_{s_{ij}}$ or its negation.

Equivalently, $k$-XORSAT requires deciding whether a set of linear equations, each of the form $\sum_{j=1}^k x_{s_{ij}}\equiv 1\; (\mod 2)$, has a solution over $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$.

Every decision problem has an associated counting problem, which (informally speaking) requires establishing the number of distinct solutions.  Such counting problems form the complexity class [#P][2].  The "hardest" problems in #P are #P-complete, as any problem in #P can be reduced to a #P-complete problem.

The counting problem associated with any NP-complete decision problem is #P-complete.  However, many "easy" decision problems (some even solvable in linear time) also lead to #P-complete counting problems.  For instance, Leslie Valiant's original 1979 paper [_The Complexity of Computing the Permanent_][3] shows that computing the permanent of a 0-1 matrix is #P-complete.  As a second example, the list of #P-complete problems in the companion paper [_The Complexity of Enumeration and Reliability Problems_][4] includes #MONOTONE 2-SAT; this problem requires counting the number of solutions to Boolean formulas in conjunctive normal form, where each clause has two variables and no negated variables are allowed.  (MONOTONE 2-SAT is of course rather trivial as a decision problem.)

Andrea Montanari has written about the partition function of $k$-XORSAT in some [lecture notes][5], and his book with Marc Mézard apparently discusses this (unfortunately I do not have a copy available to hand, and the relevant Chapter 17 is not included in Montanari's online draft).

Some counting problems are not #P-complete, but instead can be approximated in a certain sense, by means of a scheme called an FPRAS.  Jerrum, Sinclair, and collaborators have linked the existence of an FPRAS for some #P problems to the question of whether $NP = RP$.

These considerations lead to the following question:

>Is $k$-XORSAT #P-complete?  If not, does it have an FPRAS?

Note that the formula in Montanari's notes does not obviously appear to answer this question.  Just because there is a nice closed form solution, doesn't mean we can evaluate it efficiently: consider the [Tutte polynomial][6].

  [1]: http://en.wikipedia.org/wiki/Xor
  [2]: http://qwiki.stanford.edu/wiki/Complexity_Zoo%3ASymbols#sharpp
  [3]: http://dx.doi.org/10.1016/0304-3975(79)90044-6
  [4]: http://dx.doi.org/10.1137/0208032
  [5]: http://www.stanford.edu/~montanar/TEACHING/Stat316/handouts/lecture-4.pdf
  [6]: http://en.wikipedia.org/wiki/Tutte_polynomial