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 '14 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 '14 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$ – mobius dumpling Mar 23 '14 at 8:55

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.