Hard Problems of Algebraic Geometry Codes

DOI10.1109/TIT.2007.911213MaRDI QIDQ3604740zbMATH OpenOpenAlexFDO

Authors Qi Cheng

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0507026

zbMATH Keywords

Algebraic-geometric codescomplexity theorymaximum-likelihood decoding

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Abstract: The minimum distance is one of the most important combinatorial characterizations of a code. The maximum likelihood decoding problem is one of the most important algorithmic problems of a code. While these problems are known to be hard for general linear codes, the techniques used to prove their hardness often rely on the construction of artificial codes. In general, much less is known about the hardness of the specific classes of natural linear codes. In this paper, we show that both problems are NP-hard for algebraic geometry codes. We achieve this by reducing a well-known NP-complete problem to these problems using a randomized algorithm. The family of codes in the reductions are based on elliptic curves. They have positive rates, but the alphabet sizes are exponential in the block lengths.

Recommendations

• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• The intractability of computing the minimum distance of a code
• scientific article; zbMATH DE number 1284420
• On the decoding of algebraic-geometric codes

Cited in

(13)

• New constructions of MDS symbol-pair codes
• Subset sums over Galois rings
• ECC\(^2\): error correcting code and elliptic curve based cryptosystem
• On the hardnesses of several quantum decoding problems
• On the equivalence of two post-quantum cryptographic families
• On the Hardness of Decoding the Gale–Berlekamp Code
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• On Random Number Generation for Kernel Applications
• A deterministic reduction for the gap minimum distance problem (extended abstract)
• A simple deterministic reduction for the gap minimum distance of code problem
• Subset sums over Galois rings. II
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Recent progress on the elliptic curve discrete logarithm problem

This page was built for publication: Hard Problems of Algebraic Geometry Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604740)