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.