<p>Suppose I have a code $C$ over $GF(2)$. I would like to count exactly the number of codewords of $C$ of weight $k$. Here $k$ should be thought of as small compared to the dimensions of the code. </p>

<p>What is the best algorithm for this? Even exponential algorithms could be useful.</p>

CC BY-SA 3.0
2014-03-22T14:35:59.503Z
Very closely related to this (unfortunately unanswered) question: http://cstheory.stackexchange.com/questions/19335/weight-enumerator-of-a-binary-linear-code
usul
CC BY-SA 3.0
2014-03-22T14:41:46.247Z
(a reference there mentions that for general $k$ it is #P-complete, http://tel.archives-ouvertes.fr/docs/00/66/57/82/PDF/BRIQUEL_IrA_nA_e_2011_ThA_se.pdf)
usul
CC BY-SA 3.0
2014-03-23T08:55:10.737Z
Note that it's NP-hard even to determine whether there are any codewords of weight $k$ [Vardy '97]. Therefore I suspect that essentially the best algorithm to solve OP's problem is the trivial $\Theta(n^k)$ one. Maybe some techniques from lattices would be useful to prove there's no subexponential algorithm under ETH.
greg
<coding-theory>
Complexity of counting codeword length distribution
David Harris
# Complexity of counting codeword length distribution

(Asked by: username_0 on 2014-03-22)

Suppose I have a code $C$ over $GF(2)$. I would like to count exactly the number of codewords of $C$ of weight $k$. Here $k$ should be thought of as small compared to the dimensions of the code.

What is the best algorithm for this? Even exponential algorithms could be useful.

**Tags:** coding-theory

> **Comments:**
> **username_1**: Very closely related to this (unfortunately unanswered) question: http://cstheory.stackexchange.com/questions/19335/weight-enumerator-of-a-binary-linear-code  
> **username_1**: (a reference there mentions that for general $k$ it is #P-complete, http://tel.archives-ouvertes.fr/docs/00/66/57/82/PDF/BRIQUEL_IrA_nA_e_2011_ThA_se.pdf)  
> **username_2**: Note that it's NP-hard even to determine whether there are any codewords of weight $k$ [Vardy '97]. Therefore I suspect that essentially the best algorithm to solve OP's problem is the trivial $\Theta(n^k)$ one. Maybe some techniques from lattices would be useful to prove there's no subexponential algorithm under ETH.  

---

## 0 answers

