# Weight enumerator of a binary linear code

The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as

$$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$

where $$WE_{i}(\mathcal{C}) = \#\{c\in\mathcal{C} : |c| = i\}$$

is the number of codewords in $\mathcal{C}$ of Hamming weight (denoted by $|c|$) $i$.

It is known from:

That computing the weight enumerator polynomial for a binary linear code is a problem in $\mathsf{\#P}$-complete.

I wish to know if anything is known about the case of:

1. computing the $i^\text{th}$ coefficient of the weight enumerator polynomial where $i = \text{polylog}(n)$ (otherwise a naive enumeration of all binary sequences of weight $i$ and verification of those in the code would be possible).

2. Computing the weight enumerator, given the promise $WE_{i}(\mathcal{C}) \leq n^\lambda$, for $\lambda$ any constant, independent of $n$.

Does the complexity of the problem remain $\mathsf{\#P}$-hard in both cases ?

• In the first reference mentioned, kindly see [Proposition 2.7.4]. There should be some statement about the range of $w$ for which its valid right ? I would suspect if its: $w = polylog(n)$ ? – Pavithran Iyer Oct 9 '13 at 13:57
• For your second question, if all entries in the weight enumerator are polynomial, aren't there just a polynomial number of codewords? In this case computing the weight enumerator is easy. – Peter Shor Oct 9 '13 at 15:39
• @PeterShor I agree with your comment. Can I ask the hardness of computing the $i^\text{th}$ coefficient of the weight enumerator alone when the first $i$ coefficients is upper-bounded by $n^\lambda$. For $i = \alpha n$, this again implies the number of words in $\mathcal{C}$ is polynomial. What about $i = polylog(n)$ ? – Pavithran Iyer Oct 9 '13 at 16:32