2
$\begingroup$

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.

$\endgroup$

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.