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.

  • 2
    $\begingroup$ Very closely related to this (unfortunately unanswered) question: cstheory.stackexchange.com/questions/19335/… $\endgroup$
    – usul
    Mar 22, 2014 at 14:35
  • 1
    $\begingroup$ (a reference there mentions that for general $k$ it is #P-complete, tel.archives-ouvertes.fr/docs/00/66/57/82/PDF/…) $\endgroup$
    – usul
    Mar 22, 2014 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – greg
    Mar 23, 2014 at 8:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.