pith. sign in

arxiv: cs/0304044 · v1 · submitted 2003-04-30 · 💻 cs.CC

Hardness of approximating the weight enumerator of a binary linear code

classification 💻 cs.CC
keywords evaluationenumeratorhardproblemweightalphabinarycode
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the Complexity of Decoded Quantum Interferometry

    quant-ph 2025-09 unverdicted novelty 5.0

    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 ...