## Speaker:

## Institution:

## Time:

## Location:

For generalized Reed-Solomon codes, it has been proved

that the problem of determining if a

received word is a deep hole is co-NP-complete.

The reduction relies on the fact that

the evaluation set of the code can be exponential

in the length of the code --

a property that practical codes do not usually possess.

In this talk, we first present a much simpler proof of

the same result. We then consider the problem for standard

Reed-Solomon codes, i.e. the evaluation set consists of

all the nonzero elements in the field.

We reduce the problem of identifying deep holes to

deciding whether an absolutely irreducible

hypersurface over a finite field

contains a rational point whose coordinates

are pairwise distinct and nonzero.

By applying Cafure-Matera estimation of rational points

on algebraic varieties, we prove that

the received vector $(f(\alpha))_{\alpha \in \F_p}$

for the Reed-Solomon $[p-1,k]_p$, $k < p^{1/4 - \epsilon}$,

cannot be a deep hole, whenever $f(x)$ is a polynomial

of degree $k+d$ for $1\leq d < p^{3/13 -\epsilon}$.

This is a joint work with Elizabeth Murray.