  In this paper, we study (random) sequences of pseudo s-th powers, as
introduced by Erd\"os and R\'enyi in 1960. In 1975, Goguel proved that such a
sequence is almost surely not an asymptotic basis of order s. Our first result
asserts that it is however almost surely a basis of order s + x for any x > 0.
We then study the s-fold sumset sA = A + ... + A (s times) and in particular
the minimal size of an additive complement, that is a set B such that sA + B
contains all large enough integers. With respect to this problem, we prove
quite precise theorems which are tantamount to asserting that a threshold
phenomenon occurs.
