Polynomial interpolation is the following interesting problem: You are given a block box that evaluates a polynomial over $C$ with $n$ variables, and you are told that at most $t$ of its coefficients are nonzero, and its of degree $d$. You are allowed to feed inputs to the box, and your purpose is to reconstruct the polynomial.
The following famous paper gives a nonadaptive solution taking only $2t$ evaluations: http://dl.acm.org/citation.cfm?id=62241.
At the bottom it says that it can be done adapatively with $t+1$ evaluations, how can this be done?