__
Revision #1 to TR21-092 | 10th February 2023 22:55
__
#### On One-way Functions and Sparse Languages

**Abstract:**
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.

Our results are insipired by, and generalize, the recent elegant paper by Ilango,

Ren and Santhanam (ECCC'21), which presents similar characterizations for

concrete sparse languages.

__
TR21-092 | 28th June 2021 21:27
__

#### A Note on One-way Functions and Sparse Languages

**Abstract:**
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.

Our results are insipired by, and generalize, the recent elegant paper by Ilango,

Ren and Santhanam (ECCC'21), which presents similar characterizations for

concrete sparse languages.