Next: Computational Sample Complexity
Up: Sabbatical at MIT (1996-1998)
Previous: Public-Key Cryptosystems from Lattice
It is shown that there exist pairs of distributions that are
computationally indistinguishable by any probabilistic algorithms
but are easily distinguishable by circuits.
Furthermore, one distribution may be the uniform over strings
of certain length, whereas the other may have a tiny support
(of size that is any unbounded function of the string length).
Comments:
Authored by O. Goldreich and B. Meyer. Appeared in
- Theoretical Computer Science, Vol. 191 (1998), pages 215-218.
Oded Goldreich
2003-07-30