Hardness of approximating the weight enumerator of a binary linear code

Original · EN

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ʷE=PᵍapP. Also we consider the approximative evaluation of the weight enumerator. In the case of approximation with additive accuracy 2αⁿ, α is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point eπⁱ/⁴ is hard for 0<<₀≈0.88.