Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of degree $k-1$ s.t. $p(e_i) = y_i$ for all $i\in [k]$. Let $E'=\{e'_1, \dots, e'_t\}\not\subset E$ be a additive coset of a subgroup of $E$ (i.e. $t < k$).
Problem. Given $y$ as input, can we compute $p(e'_i)$ for all $i\in [t]$ in time $O_{\log|\mathbb{F}|}(k + t\;\mathrm{polylog}\;k)$? That is, if $t = k / \mathrm{polylog}(k)$, the computation would run in time $O_{\log|\mathbb{F}|}(k)$. Note that if $t = O(k)$, FFT solves this problem in time $O_{\log|\mathbb{F}|}(k + k \;\mathrm{polylog}\; k) = O(k \;\mathrm{polylog}\; k)$.
Relaxation. It would be still be interesting to solve this problem over any finite field $\mathbb{F}$ and any (disjoint) subsets $E,E'\subset \mathbb{F}$ of size $k,t$, respectively, in time $O_{\log|\mathbb{F}|}(k\log\log k + t\;\mathrm{polylog}\;k)$.
