This note is a culmination of a line of work [LP20,...,IRS21]
that related the existence of hard-on-the-average problems that
are *morally sparse* to the existence of one-way functions.
In the current work,
the morally sparse aspects takes the most transparent form.

In retrospect, this reminds me of my own note on computational indistinguishability in which an equivalence is proved between the existence of pseudorandom generators (equiv., of one-way functions) and the existence of samplable distributions that are computationally indistinguishable and yet statistically far apart. The point is that a relatively sparse problem (i.e., sparse with respect to the distribution on which it is hard) as in the first item of the abstract (below) yields a pair of disjoint distributions (one on Yes-instances and one on No-instances) that are computational indistinguishable although typically elements in one distribution have significantly larger probability weight than in the other. Needless to say, this pair of distributions is not necessarily sampleable (i.e., it falls short from the condition of the foregoing note), but if one-way functions do not exist then we can distinguish these two distributions by approximating the probability weight of instances (by inverting the sampling procedure). Of course, the foregoing note is not really used; it merely plays a role in my way of thinking about this result.

The **take home message** is that the existence of a
relatively sparse problem as in the first item below
implies that it must be typically hard to estimate
the probability weight of elements in the sampled distribution;
that is, that the sampling process is typically
hard to invert, and yields a one-way function.
On the other hand, the existence of pseudorandom generators
implies a problem as in the first item
(e.g., consider the set of pseudorandom outputs and a distribution
that is pseudorandom with probability half and totally random otherwise).

We show equivalence between the existence of one-way functions and the existence of a \emph{sparse} language that is hard-on-average w.r.t. some efficiently samplable ``high-entropy'' distribution. In more detail, the following are equivalent:

- The existentence of a $S(\cdot)$-sparse language $L$ that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq 4\log n$;
- The existentence of a $S(\cdot)$-sparse language $L \in \NP$, that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq n/3$;
- The existence of one-way functions.

Available from ECCC TR21-092

Back to list of Oded's choices.