期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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()-sparse language L that is hard-on-average with respect to some samplable distribution with Shannon entropy h() such that h(n)−log(S(n))4logn ; - The existentence of a S()-sparse language L\NP, that is hard-on-average with respect to some samplable distribution with Shannon entropy h() such that h(n)−log(S(n))n3 ; - 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.
