  Let $\mathbb{F}_q$ be the finite field of size $q$ and let $\ell:
\mathbb{F}_q^n \to \mathbb{F}_q$ be a linear function. We introduce the {\em
Learning From Subset} problem LFS$(q,n,d)$ of learning $\ell$, given samples $u
\in \mathbb{F}_q^n$ from a special distribution depending on $\ell$: the
probability of sampling $u$ is a function of $\ell(u)$ and is non zero for at
most $d$ values of $\ell(u)$. We provide a randomized algorithm for
LFS$(q,n,d)$ with sample complexity $(n+d)^{O(d)}$ and running time polynomial
in $\log q$ and $(n+d)^{O(d)}$. Our algorithm generalizes and improves upon
previous results \cite{Friedl, Ivanyos} that had provided algorithms for
LFS$(q,n,q-1)$ with running time $(n+q)^{O(q)}$. We further present
applications of our result to the {\em Hidden Multiple Shift} problem
HMS$(q,n,r)$ in quantum computation where the goal is to determine the hidden
shift $s$ given oracle access to $r$ shifted copies of an injective function
$f: \mathbb{Z}_q^n \to \{0, 1\}^l$, that is we can make queries of the form
$f_s(x,h) = f(x-hs)$ where $h$ can assume $r$ possible values. We reduce
HMS$(q,n,r)$ to LFS$(q,n, q-r+1)$ to obtain a polynomial time algorithm for
HMS$(q,n,r)$ when $q=n^{O(1)}$ is prime and $q-r=O(1)$. The best known
algorithms \cite{CD07, Friedl} for HMS$(q,n,r)$ with these parameters require
exponential time.
