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

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

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

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

<p>It is known from:</p>

<ol>
<li><p><a href="http://tel.archives-ouvertes.fr/docs/00/66/57/82/PDF/BRIQUEL_IrA_nA_e_2011_ThA_se.pdf" rel="noreferrer">Complexity issues in counting, polynomial evaluation and zero finding</a></p></li>
<li><p><a href="http://arxiv.org/pdf/0704.3683.pdf" rel="noreferrer">The Complexity of Weighted Boolean #CSP</a></p></li>
</ol>

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

<p>I wish to know if anything is known about the case of:</p>

<ol>
<li><p>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).</p></li>
<li><p>Computing the weight enumerator, given the promise $WE_{i}(\mathcal{C}) \leq n^\lambda$, for $\lambda$ any constant, independent of $n$.</p></li>
</ol>

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

CC BY-SA 3.0
2013-10-09T13:57:45.377Z
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
CC BY-SA 3.0
2013-10-09T15:39:57.717Z
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 
CC BY-SA 3.0
2013-10-09T16:32:12.667Z
@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
<cc.complexity-theory><counting-complexity><coding-theory>
Weight enumerator of a binary linear code
Pavithran Iyer
# Weight enumerator of a binary linear code

(Asked by: username_0 on 2013-10-09)

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:

1. [Complexity issues in counting, polynomial evaluation and zero finding](http://tel.archives-ouvertes.fr/docs/00/66/57/82/PDF/BRIQUEL_IrA_nA_e_2011_ThA_se.pdf)
2. [The Complexity of Weighted Boolean #CSP](http://arxiv.org/pdf/0704.3683.pdf)

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 ?

**Tags:** cc.complexity-theory, counting-complexity, coding-theory
> **Comments:**
> **username_0**: 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)$ ?  
> **username_1**: 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.  
> **username_0**: @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)$ ?  

---

## 0 answers

