Computer Science – Information Theory
Scientific paper
2005-07-08
Computer Science
Information Theory
13 pages, No figure
Scientific paper
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.
No associations
LandOfFree
Hard Problems of Algebraic Geometry Codes 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 Hard Problems of Algebraic Geometry Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hard Problems of Algebraic Geometry Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-374769