New answers tagged polynomial-time
3
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