complexity of deciding whether there's a small polynomial with a given root
Here is an algorithm that solves the problem in time
$$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$
The tildes hide $(\log p)^{O(1)}$ factors coming from operations in $\mathbb F_p$ and from implementation of sets by, say, min-heaps.

First, observe that the answer is always YES if $d+1\ge\frac{\log(p+1)}{\log(r+1)}$: there are $(r+1)^{d+1}\ge p+1$ polynomials $P$ of degree at most $d$ with coefficients in $\{0,\dots,r\}$, hence by the pigeonhole principle, there exist two such polynomials $P_0\ne P_1$ such that $\overline{P_0}(f)=\overline{P_1}(f)$. Then $P=P_0-P_1$ satisfies the requirements.

Thus, we may assume without loss of generality
$$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$
Then (assuming $r\ge1$) 
$$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$
hence it suffices to find an algorithm working in time
$$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$

For any $i\le d+1$, let
$$V_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P)&lt;i,\|P\|_\infty\le r\}.$$
Using this notation, the problem is equivalent to finding out if $0\in V_{d+1}$, and we can compute $V_i$ using a simple recurrence. The whole algorithm looks like this:


If $r=0$, output NO.
If $d+1\ge\frac{\log(p+1)}{\log(r+1)}$, output YES.
For each $j=\lceil\log(d+2)\rceil,\dots,1$, compute $V_{\lfloor(d+1)2^{-j}\rfloor}$ and $f^{\lfloor(d+1)2^{-j}\rfloor}$ by using the recurrences
$$\begin{align*}
V_0&amp;=\varnothing,\\
V_{2i}&amp;=V_i\cup\bigl\{a+f^ib:a\in V_i\cup\{0\},b\in V_i\bigr\},\\
V_{2i+1}&amp;=V_{2i}\cup\bigl\{a+f^{2i}b:a\in V_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\},
\end{align*}$$
where all the arithmetic operations are modulo $p$.
If $d$ is even, compute $V_{\lceil(d+1)/2\rceil}$ from $V_{\lfloor(d+1)/2\rfloor}$ as above.
If $0\in V_{\lceil(d+1)/2\rceil}$, output YES.
For each $a\in V_{\lceil(d+1)/2\rceil}$, if $-af^{\lceil(d+1)/2\rceil}\in V_{\lfloor(d+1)/2\rfloor}$, then output YES.
Output NO.


It should be clear from the discussion above that the algorithm is correct. Moreover, we have
$$|V_i|\le(2r+1)^i,$$
and since these bounds form a geometric series, it is easy to see that the time needed to compute $V_i$ using the above recurrences is also
$$\tilde O\Bigl((2r+1)^i\Bigr).$$
Thus, the algorithm runs in time
$$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$