  We consider the problem of approximating certain combinatorial polynomials.
First, we consider the problem of approximating the Tutte polynomial of a
binary matroid with parameters q>= 2 and gamma. (Relative to the classical
(x,y) parameterisation, q=(x-1)(y-1) and gamma=y-1.) A graph is a special case
of a binary matroid, so earlier work by the authors shows inapproximability
(subject to certain complexity assumptions) for q>2, apart from the trivial
case gamma=0. The situation for q=2 is different. Previous results for graphs
imply inapproximability in the region -2<=gamma<0, apart from at two "special
points" where the polynomial can be computed exactly in polynomial time. For
binary matroids, we extend this result by showing (i) there is no FPRAS in the
region gamma<-2 unless NP=RP, and (ii) in the region gamma>0, the approximation
problem is hard for the complexity class #RHPi_1 under approximation-preserving
(AP) reducibility. The latter result indicates a gap in approximation
complexity at q=2: whereas an FPRAS is known in the graphical case, there can
be none in the binary matroid case, unless there is an FPRAS for all of
#RHPi_1. The result also implies that it is computationally difficult to
approximate the weight enumerator of a binary linear code, apart from at the
special weights at which the problem is exactly solvable in polynomial time. As
a consequence, we show that approximating the cycle index polynomial of a
permutation group is hard for #RHPi_1 under AP-reducibility, partially
resolving a question that we first posed in 1992.
