Consider the finite field $\mathbb F_q$ where $q=2^n$ and $n \to \infty$. Now given $t = O(1)$ and $x_1,\ldots,x_t,y_1,\ldots,y_t$ where $\forall i \ne j,x_i \ne x_j,y_i \ne y_j$, do one has a permutation polynomial $f \in \mathbb F_q[x]$ such that $\mathrm{deg}(f)=O_t(1)$ and $\forall i,f(x_i) = y_i$?
There exist related results but measuring the complexity of $f$ in terms of linear combinations of $x^{q-2}$ instead of the degree.