Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-067 | 20th December 1996 00:00

Computational Indistinguishability -- Algorithms vs. Circuits.

RSS-Feed




TR96-067
Authors: Oded Goldreich, Bernd Meyer
Publication: 20th December 1996 10:43
Downloads: 3209
Keywords: 


Abstract:

We present a simple proof to the existence of a probability ensemble
with tiny support which cannot be distinguished from the uniform ensemble
by any recursive computation.
Since the support is tiny (i.e, sub-polynomial),
this ensemble can be distinguish from the uniform ensemble
by a (non-uniform) family of small circuits.
It also provides an example of an ensemble which cannot be (recursively)
distinguished from the uniform by one sample, but can be so distinguished
by two samples.
In case we only wish to fool probabilistic polynomial-time algorithms
the ensemble can be constructed in slightly super-exponential time.



ISSN 1433-8092 | Imprint