Relation between degree and Hamming distance Let $\mathbb{F}$ be a finite field. Let $S \subset \mathbb{F}$ be some non-empty set. Define the relative Hamming distance between two function $f,g: S \to \mathbb{F}$ by
 $$
 \Delta_S (f, g) := \frac{1}{|S|} | \{ s \in S: f(s) \neq g(s) \} |.   
 $$
Fix some $0< \rho <1$. Let $\mathrm{RS}[\mathbb{F}, S, \rho]$ be the set of functions on $S$ who are evaluations of polynomials of degree $<\rho |S|$:
$$
\mathrm{RS}[\mathbb{F}, S, \rho] := \{ f: S \to \mathbb{F}:\ \exists p \in \mathbb{F} [x^{< \rho|S|} ]   \ \   f = p|_S \}. 
$$ 
For a function $f: S \to \mathbb{F}$, let 
$$
\delta(f) := \Delta_S(f, \mathrm{RS}[\mathbb{F}, S, \rho]) = \min \{ \Delta_S(f,g): g \in  \mathrm{RS}[\mathbb{F}, S, \rho] \}, 
$$
and let $\mathrm{deg}(f)$ be the degree of the interpolant of $f$ with respect to the set $S$.
By definition, $\delta(f) = 0$ if and only if $f \in \mathrm{RS}[\mathbb{F}, S, \rho]$ if and only if $\mathrm{deg}(f)<\rho|S|$. 

My question is, how are $\delta(f)$ and $\mathrm{deg}(f)$ related? 

Edit: after thinking about for a little bit, I came to the opposite conclusion: the closer a non-code word is to $\mathrm{RS}[\mathbb{F}, S, \rho]$, the higher its degree. 
Claim: For any $\rho< m< 1$ and $f:S \to \mathbb{F}$, $$0<\delta(f)<1-m \Longrightarrow \mathrm{deg}(f)>m|S|.$$
Proof: Suppose there exists $g \in \mathrm{RS}[\mathbb{F}, S, \rho]$ such that $f(x) = g(x)$ on a set of size $m|S|$, $\rho < m < 1$.  If $\mathrm{deg}(f) < m|S|$, then by unique interpolation we have $f=g$. In other words, if $f \notin \mathrm{RS}[\mathbb{F}, S, \rho]$ and there exists a $g \in \mathrm{RS}[\mathbb{F}, S, \rho]$ such that $\Delta_S(f, g) < 1-m$ then $\mathrm{deg}(f) > m |S|$. 

How about the converse claim? that is, is it true that if $\mathrm{deg}(f)>m |S|$ then there exists $g \in \mathrm{RS}[\mathbb{F}, S, \rho]$ with $\Delta_S (f, g) < 1-m$?

 A: $\newcommand{\abs}[1]{\left|#1\right|}$
If your $\rho$ and $m$ are close enough, so that $\lfloor{m\abs{S}}\rfloor=\lfloor \rho\abs{S}\rfloor$ then the converse definitely holds. Just take $g$ to be interpolant of $f$ on $S$, and $\Delta_{S}(f,g)=0$ by definition.
Otherwise, it seems like the converse can easily fail unless you pose some assumptions on $\rho$. There's just too much freedom with respect to $\rho$. For example, if you take $\rho$ small enough so that $\rho<\frac{1}{\abs{S}}$, then the statement ``$\exists g\in\mathrm{RS}(\mathbb F,S, \rho)$ such that $\Delta_S(f,g)<1-m$'' is equivalent to the fact that $f$ has a level set of cardinality $>m\abs{S}$. Indeed, if $\rho<\frac{1}{\abs{S}}$ then, by definition, the elements of $\mathrm{RS}(\mathbb{F},S,\rho)$ are just the restrictions to $S$ of constant polynomials, and, by definition of the Hamming distance, for $\lambda\in \mathbb F$, we have that
$$\Delta_{S}(f,\lambda)<1-m\quad\iff\abs{f^{-1}(\lambda)}=\abs{\lbrace s\in S: f(s)=\lambda\rbrace}=\abs{S}(1-\Delta_{S}(f,\lambda))>m\abs{S}.$$
Now, to fins a counterexample, we just need to find a set $S$, a number $\abs{S}^{-1}<m<1$ and a function $f:S\to \mathbb F$ such that $\deg(f)>m\abs{S}$ and $f$ has level sets of size $\le m\abs{S}$.
My idea is to take $S=\mathbb F\setminus\lbrace 0\rbrace$, $m=\frac{1}{2}$, and $f:S\to\mathbb F$ defined as follows. Let $\eta\in \mathbb F$ be a fixed non-square in $S$ and let 
$$f(s)=\begin{cases}0&\exists x\in \mathbb F(s=x^2) \\
-1&x=\eta\\
1&\text{otherwise} \end{cases}.$$
So, assuming $\mathrm{Char}(\mathbb F)>2$, the level sets of $f$ are of cardinality in the range $[0,\frac{1}{2}\abs{S}]$, and hence
$$\delta(f)=\Delta_S(f,\mathrm{RS}(\mathbb F,S,\rho))=\frac{1}{2}\abs{S},$$
whenever $\rho<\frac{1}{\abs{S}}$. We are just left to show that $f$ has degree $>\frac{1}{2}\abs{S}$. 
Assume otherwise, and that $\abs{\mathbb F}>3$, and let $p\in\mathbb F[x]$ be a polynomial of degree $\le \frac{1}{2}\abs{S}$ such that $p\mid_S=f$. In particular, $p\mid_{S^2}$ ($S^2=$ the set of squares in $S$) is identically zero, and hence (since $\mathbb F[x]$ is a PID) $p$ is divisible by $\prod_{s\in S^2}(x-s)$ and hence equal to it (since they have the same degree), up to multiplication by a constant. We claim that $p(s')=1$ for all $s'\in S\setminus S^2$, and therefore the restriction $p(\eta)=-1$ does not hold and $f\ne p\mid_S$. This holds because the set of non-squares is a coset of $S^\times$ in $S$ (considered as a subgroup of $S=\mathbb F^\times$). Thus, given $\nu_1,\nu_2\in S\setminus S^2$, we have that $\nu_1=\nu_2s'$ for some $s'\in S^2$, and hence 
$$p(\nu_1)=\prod_{s\in S^2}(\nu_1-s)=\prod_{s\in S^2}((\nu_2- s'^{-1} s)s')=(s')^{\abs{S^2}}p(\nu_2)=p(\nu_2),$$
since multiplication by $s'$ is a permutation of $S^2$, and $(s')^{\abs{S^2}}=1$. Thus $p$ is constant on the coset $S\setminus S^2$. In particular, since the assumption $\abs{\mathbb F}>3$ implies that $S\setminus S^2$ contains element distinct from $\eta$, it follows that $p\equiv 1$ on $S\setminus S'$, a contradiction. Therefore no interpolant of $f$ of degree $\frac{1}{2}\abs{S}$ exists, and $\deg(f)>\frac{1}{2}\abs{S}$.
