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 and acknowledge you have read our privacy policy.