In [IEEE Trans. Information Theory, vol. 67, nr. 1 (2021)] we have presented error-correcting algorithms that interpolate sparse univariate polynomials from values at arguments which the algorithms compute. We have assumed that the input polynomials are sparse in terms that are powers of the variable (standard basis) or sparse in Chebyshev basis polynomials. We recover all polynomials of sparsity $\le B$ that from our $N$ input points interpolate at least $N-E$ of the points, that is, correct $\le E$ errors in the values at the error capacity $E/N$. Our IEEE Transactions algorithms have, roughly, an error capacity of $0.75/B$ for power basis and $0.66/B$ for Chebyshev basis. We present algorithms which randomly select values from sufficiently large finite sets before evaluation, and then return the sparse interpolant in a list of valid interpolants with high probability. The error capacity of our algorithms for both power and Chebyshev bases is, roughly, $1/B$. More precisely, we recover the interpolant from $N = \lfloor E/2 + 1 \rfloor (2B+1)$ values with probability $\ge 1-\epsilon$ when sampling from sets that have $\ge 16 \lfloor E/2 + 1 \rfloor D B^2/\epsilon$ elements, where $D$ is an upper bound on the degree of the polynomial. Our algorithms are based on Prony's interpolation algorithm and perform exact arithmetic in the field of scalars, which for Chebyshev basis is required to have characteristic $\ne 2$. The running time is polynomial in the bounds $B,E$ and $D$ or $\log(D)$, depending on the representation of the scalar field elements. In the special case of evaluations at positive real numbers, as a consequence of Descartes's Rule of Signs, our algorithms recover a unique real interpolant for $B,E \ge 2$, and for sparsity in both standard and Chebyshev bases can be de-randomized to deterministic versions.