Hardness of approximating the weight enumerator of a binary linear code
read the original abstract
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$.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
On the Complexity of Decoded Quantum Interferometry
DQI resists classical simulation by locating high-probability outputs but is simulable at a low level of the polynomial hierarchy, constructively solves a MacWilliams-based coding bound, and corresponds to low-energy ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.