We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena cannot exist for non-uniform classes of
distinguishers, say, polynomial-size circuits).
It was also known that there exist pairs of ensembles which may be efficiently
distinguished based on {\em two}\/ samples but cannot be efficiently
distinguished based on a {\em single}\/ sample.
In contrast, it was not known whether the distinguishing power increases
when one moves from two samples to polynomially-many samples.

We show the existence of pairs of ensembles which may be efficiently
distinguished given $k+1$ samples but cannot be efficiently
distinguished given $k$ samples, where $k$ can be any function
bounded above by a polynomial in the security parameter.

In course of establishing the above result,
we prove several technical lemmas regarding polynomials and graphs.
We believe that these may be of independent interest.