next up previous
Next: On the Limits of Up: Sabbatical at MIT (1996-1998) Previous: Another proof that BPP

Computational Indistinguishability: A Sample Hierarchy

This paper establishes the existence of pairs of distributions that can be efficiently distinguished given k+1 samples but cannot be distinguished given k samples, where in both cases we refer to uniform algorithms.


Comments: Authored by O. Goldreich and M. Sudan. Appeared in



Oded Goldreich
2003-07-30