Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-092 | 28th June 2021 21:27

A Note on One-way Functions and Sparse Languages

RSS-Feed




TR21-092
Authors: Yanyi Liu, Rafael Pass
Publication: 2nd July 2021 04:24
Downloads: 140
Keywords: 


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.



ISSN 1433-8092 | Imprint