## Speaker:

## Institution:

## Time:

## Location:

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.