Professor Qi Cheng


University of Oklahoma


Wednesday, June 8, 2005 - 3:00pm


MSTB 256

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 have positive rates, but
the alphabet sizes are exponential in the block lengths.