  A recent sequence of works, initially motivated by the study of the nonlocal
properties of entanglement, demonstrate that a source of
information-theoretically certified randomness can be constructed based only on
two simple assumptions: the prior existence of a short random seed and the
ability to ensure that two black-box devices do not communicate (i.e. are
non-signaling). We call protocols achieving such certified amplification of a
short random seed randomness amplifiers.
  We introduce a simple framework in which we initiate the systematic study of
the possibilities and limitations of randomness amplifiers. Our main results
include a new, improved analysis of a robust randomness amplifier with
exponential expansion, as well as the first upper bounds on the maximum
expansion achievable by a broad class of randomness amplifiers. In particular,
we show that non-adaptive randomness amplifiers that are robust to noise cannot
achieve more than doubly exponential expansion. Finally, we show that a wide
class of protocols based on the use of the CHSH game can only lead to (singly)
exponential expansion if adversarial devices are allowed the full power of
non-signaling strategies. Our upper bound results apply to all known
non-adaptive randomness amplifier constructions to date.
