Hardness of approximating the weight enumerator of a binary linear code

2003/04/30 by M. Vyalyi, M. N. Vyalyi, Vyalyi, M. N. · 5 citations
Computer Science · Engineering · #Advanced Wireless Network Optimization #Coding theory and cryptography #Computational Complexity (cs.CC) #Error Correcting Code Techniques #F.1.3 #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.cs/0304044

7 pages

arxiv created 2003/04/30 · openalex publication_date 2003/04/30 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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^αn, α is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point e^πi/4 is hard for 0

Cited by

• Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits
• Peaked quantum advantage using error correction
• On the Complexity of Decoded Quantum Interferometry
• Hardness of decoding quantum stabilizer codes
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers

Related

• The joint weight enumerator of an LCD code and its dual
• Complete weight enumerators of a class of linear codes with four or five weights
• On the complete weight enumerators of some linear codes with a few weights
• Complete weight enumerators for several classes of two-weight and three-weight linear codes
• Complete weight enumerators of two classes of linear codes