5
$\begingroup$

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

  2. The Complexity of Weighted Boolean #CSP

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 ?

$\endgroup$
  • $\begingroup$ 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)$ ? $\endgroup$ – Pavithran Iyer Oct 9 '13 at 13:57
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Oct 9 '13 at 15:39
  • $\begingroup$ @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)$ ? $\endgroup$ – Pavithran Iyer Oct 9 '13 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.