Next: On the Limits of
Up: Sabbatical at MIT (1996-1998)
Previous: Another proof that BPP
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
- Proc. of the 13th CCC, pages 24-33, 1998.
- JCSS,
Vol. 59, pages 253-269, 1999.
Oded Goldreich
2003-07-30