Hardness of approximating the weight enumerator of a binary linear code

Details Hardness of approximating the weight enumerator of a binary linear code Hardness of approximating the weight enumerator of a binary linear code

2003-04-30

arxiv.org/abs/cs/0304044v1

Computer Science

Computational Complexity

7 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Hardness of approximating the weight enumerator of a binary linear code does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hardness of approximating the weight enumerator of a binary linear code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardness of approximating the weight enumerator of a binary linear code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31489