Consider a sparse polynomial $f \in \mathbb{F}_p[x]$, of maximum degree $k$, with a known support of $t$ terms. That is, we know a set $I \subseteq \mathbb{N}$ such that $\#I = t$ and $f(x) = \sum_{i \in I} {a_i x^i}$. Some of the $a_i$ may be zero. $p$ is much larger than $t$ or $k$.
What is the size of a minimal set $U$ of points in $\mathbb{F}_p$ such that knowing $f(u)$ for each $u \in U$ determines $f$?
(Clarification: I'm looking for how to choose a minimal set, as well as its size.)
Intuitively it should be $t$ — but is that right, are there any side-conditions, and how do I prove it? Also, if it matters which points I choose to minimize $\#U$, how should I choose them?
The dense case is proven here.
Similar, but not identical question: Interpolating $t$-sparse polynomial with $t+1$ evaluations. It's not identical because the support is known, and because in this context I don't need to actually do the interpolation, only to prove that there is a unique solution.
A somewhat related paper is What Can (and Can't) we Do with Sparse Polynomials, which references On the bit-complexity of sparse polynomial and series multiplication.
(If you're curious, this problem arises in the context of optimizing Toom-Cook-style multiplication of sparse elements of $\mathbb{F}_{p^{12}}$ obtained from line functions, during computation of cryptographic pairings.)
Being able to determine $f$ boils down to whether or not the submatrix of the Vandermonde matrix with indices in $I$ is invertible or not. This is not always true but we can construct examples where it is:
Consider $p=8191$, $k = 13$, $I = \{0, 13\}$ and $U = \{1_{p}, 2_{p}\}$.
Polynomials $1_p + x^{13}$ and $2_p x^{13}$ both take values $\{2_{p}, 2_{p}\}$ on $U$.
Whenever you can have points in $U$ related by a $i$th root of unity with $i$ in $I$ you can construct a singular Vandermonde matrix.
Are you looking for the number of points you need such that whenever $U$ has that many points you can reconstruct the polynomial, or are you looking for a minimal set of points which lets you reconstruct any polynomial?
In which case, consider $g \in \mathbb{F}_p$ and $U = \{x_0,\ldots,x_{t-1}\} = \{1_p,g,g^2,\ldots,g^{t-1}\}$
The Vandermonde matrix becomes $V_{i,j} = (g^{j})^i = (g^{i})^j$ which is also the Vandermonde matrix for polynomials of degree $t-1$ taken at points $g^i$ for $i$ in $I$. So long as they these points take distinct values, the polynomial can be recovered.