Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that:

  1. $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$.

  2. $A_{n}$ is in $\#P-Complete$, equivalently, computing $A_{n}$ is hard for $PH$, under polytime Turing reductions. See here and here.

What about the computational hardness of $A_{i}$ where $i = polylog(n)$ ? Are there results of the type: $A_{\lceil \log_{2}^{k}n \rceil} \in \Sigma^{P}_{k-1}$ ?

This question may be related to this stack exchange question.


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.