In the context of statistical physics, Chandrasekharan and Wiese recently
introduced the \emph{fermionant} $\Ferm_k$, a determinant-like quantity where
each permutation $\pi$ is weighted by $-k$ raised to the number of cycles in
$\pi$. We show that computing $\Ferm_k$ is #P-hard under Turing reductions for
any constant $k > 2$, and is $\oplusP$-hard for $k=2$, even for the adjacency
matrices of planar graphs.

Approximate algebraic structures play a defining role in arithmetic
combinatorics and have found remarkable applications to basic questions in
number theory and pseudorandomness. Here we study approximate representations
of finite groups: functions f:G -> U_d such that Pr[f(xy) = f(x) f(y)] is
large, or more generally Exp_{x,y} ||f(xy) - f(x)f(y)||^2$ is small, where x
and y are uniformly random elements of the group G and U_d denotes the unitary
group of degree d.

We present a simple, natural #P-complete problem. Let G be a directed graph,
and let k be a positive integer. We define q(G;k) as follows. At each vertex v,
we place a k-dimensional complex vector x_v. We take the product, over all
edges (u,v), of the inner product <x_u,x_v>. Finally, q(G;k) is the expectation
of this product, where the x_v are chosen uniformly and independently from all
vectors of norm 1 (or, alternately, from the Gaussian distribution). We show
that q(G;k) is proportional to G's cycle partition polynomial, and therefore
that it is #P-complete for any k>1.