New answers tagged


Even relaxing the "computationally efficient" requirement, it is information-theoretically impossible. We will use the following "folklore" fact, which can be viewed as a consequence of the birthday paradox: Fact. Distinguishing with probability say $2/3$ between (1) the uniform distribution on $[d]$ and (2) a distribution on a subset of ...

Top 50 recent answers are included