Hardness of approximating the weight enumerator of a binary linear code
<|reference_start|>Hardness of approximating the weight enumerator of a binary linear code: We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is an oracle answering the solution of the evaluation problem then P^WE=P^GapP. Also we consider the approximative evaluation of the weight enumerator. In the case of approximation with additive accuracy $2^{\alpha n}$, $\alpha$ is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point $e^{\pi i/4}$ is hard for $0<\al<\al_0\approx0.88$.<|reference_end|>
@article{vyalyi2003hardness,
    title={Hardness of approximating the weight enumerator of a binary linear code},
    author={M.N.Vyalyi},
    journal={arXiv preprint arXiv:cs/0304044},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304044},
    primaryClass={cs.CC}
}