Suppose that $f$ is a function from the prime-order field $\mathbb F_p$ to the field itself. Considering the evaluation map $P\mapsto P(x,f(x))$ and comparing the dimensions, it is easy to show that there exists a bivariate polynomial $P$ of total degree $d<\sqrt{2p}$ such that $P(x,f(x))=0$ for each $x\in\mathbb F_p$.
What I need instead is a low-degree polynomial $P$ such that $P(x,f(x))=0$ holds for all, but exactly one value of $x\in\mathbb F_p$.
In general, such a polynomial may fail to exist; say, to have $P(x,x)=0$ for all $x\in\mathbb F_p$ with one exception, we need $\deg P\ge p-1$.
What should one require from $f$ to ensure the existence of a polynomial $P$ with, say, $\deg P=O(p^{1/2+\varepsilon})$, such that $P$ vanishes on all, but exactly one point $(x,f(x))$, $x\in\mathbb F_p$?
To give the question a more precise shape, suppose that there is a partition $\mathbb F_p=S_1\cup\dotsb\cup S_n$, and a system of (univariate) polynomials $Q_1,\dotsc,Q_n$, such that $f$ coincides with $Q_k$ on $S_k$, for each $k\in[1,n]$. If in this case $P(x,f(x))$ vanishes for all, but one element $x\in\mathbb F_p$, then $$ \textstyle \deg P\ge \min \left\{ \frac{|S_k|-1)}{\deg Q_k}\colon 1\le k\le n \right\}. $$ Thus, a necessary condition for $P$ of degree $\deg P=O(p^{1/2+\varepsilon})$ to exist is that if $f$ is "piecewise polynomial", as we have just described, then $|S_k|=O(p^{1/2+\varepsilon}\deg Q_k)$ for each $k\in[1,n]$. Is some form of this condition also sufficient?
Making the even stronger assumption that $$ | \{ x\in\mathbb F_p\colon f(x)=Q(x) \} | = O(p^{1/2+\varepsilon} \deg Q) $$ for any (non-zero) polynomial $Q$, can we conclude that there exists a polynomial $P$ with $\deg P=O(p^{1/2+\varepsilon})$ such that $P$ vanishes on all, but exactly one point $(x,f(x)),\ x\in\mathbb F_p$?
