It is a long-standing open question whether the average-case hardness of NP implies the existence of a one-way function. The hypothetical world in which this does not hold is called Pessiland, which is the most pessimistic among Impagliazzo’s five possible worlds. In this paper, we present the first ”sharp” characterization of Pessiland: (i) NP is hard on average if and only if the minimum description length of programs in agnostic learning is hard to approximate on average with an approximation factor ℓ / polylog(ℓ), where ℓ is a new complexity measure of a distribution called advice complexity of sampling; and (ii) a one-way function does not exist if and only if the minimum description length of programs in agnostic learning is easy to approximate on average with an approximation factor O(ℓ). In particular, Pessiland is ruled out if and only if the small quantitative gap in approximation factors ℓ/polylog(ℓ) and O(ℓ) is closed.

The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any samplable distribution admits a coding theorem for randomized time-bounded Kolmogorov complexity$(\text{rK}^{\text{poly}})$is open and a common bottleneck in the recent literature of meta-complexity. Previous works bypassed this issue by considering probabilistic Kolmogorov complexity$(\text{pK}^{\text{poly}})$, in which public random bits are assumed to be available. In this paper, we present an efficient coding theorem for randomized Kolmogorov complexity under the non-existence of one-way functions, thereby removing the common bottleneck. This enables us to prove$\text{rK}^{\text{poly}}$counterparts of virtually all the average-case results that were proved only for$\text{pK}^{\text{poly}}$, and enables the resolution of the following concrete open problems. 1)The existence of a one-way function is characterized by the failure of average-case symmetry of information for randomized time-bounded Kolmogorov complexity, as well as a conditional coding theorem for randomized time-bounded Kolmogorov complexity. This resolves the open problem of Hirahara, Ilango, Lu, Nanashima, and Oliveira (STOC'23). 2)Hirahara, Kabanets, Lu, and Oliveira (CCC'24) showed that randomized time-bounded Kolmogorov complexity admits search-to-decision reductions in the errorless average-case setting over any samplable distribution, and left open whether a similar result holds in the error-prone setting. We resolve this question affirmatively, and as a consequence, characterize the existence of a one-way function by the average-case hardness of computing$\text{rK}^{\text{poly}}$with respect to an arbitrary samplable distribution, which is an$\text{rK}^{\text{poly}}$analogue of the$\text{pK}^{\text{poly}}$characterization of Liu and Pass (CRYPTO'23). The key technical lemma is that any distribution whose next bits are efficiently predictable admits an efficient encoding and decoding scheme, which could be of independent interest to data compression.

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge (CZK) proofs for all languages in NP. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of zero knowledge. Specifically, we prove that the following are equivalent: - A one-way function exists. - NP ⊆ CZK and NP is hard in the worst case. - CZK is hard in the worst case and the problem GapMCSP of approximating circuit complexity is in CZK. The characterization above also holds for statistical and computational zero-knowledge argument systems. We further extend this characterization to a proof system with knowledge complexity O(logn). In particular, we show that the existence of a one-way function is characterized by the worst-case hardness of CZK if GapMCSP has a proof system with knowledge complexity O(logn). We complement this result by showing that NP admits an interactive proof system with knowledge complexity ω(logn) under the existence of an exponentially hard auxiliary-input one-way function (which is a weaker primitive than an exponentially hard one-way function). We also characterize the existence of a robustly-often nonuniformly computable one-way function by the nondeterministic hardness of CZK under the weak assumption that PSPACE ⊈AM. We present two applications of our results. First, we simplify the proof of the recent characterization of a one-way function by NP-hardness of a meta-computational problem and the worst-case hardness of NP given by Hirahara (STOC’23). Second, we show that if NP has a laconic zero-knowledge argument system, then there exists a public-key encryption scheme whose security can be based on the worst-case hardness of NP. This improves previous results which assume the existence of an indistinguishable obfuscation.

Pessiland is one of Impagliazzo’s five possible worlds in which NP is hard on average, yet no one-way function exists. This world is considered the most pessimistic because it offers neither algorithmic nor cryptographic benefits.In this paper, we develop a unified framework for constructing strong learning algorithms under the nonexistence of a one-way function, indicating a positive aspect of Pessiland. Using our framework, we improve the learning algorithm for adaptively changing distributions, which was introduced by Naor and Rothblum (ICML’06). Although the previous learner assumes the knowledge of underlying distributions, our learner is universal, i.e., does not assume any knowledge on distributions, and has better sample complexity. We also employ our framework to construct a strong agnostic learner with optimal sample complexity, which improves the previous PAC learner of Blum, Furst, Kearns, and Lipton (Crypto’93). Our learning algorithms are worst-case algorithms that run in exponential time with respect to computational depth, and as a by-product, we present the first characterization of the existence of a one-way function by the worst-case hardness of some promise problem in AM. As a corollary of our results, we establish the robustness of average-case learning, that is, the equivalence among various average-case learning tasks, such as (strong and weak) agnostic learning, learning adaptively changing distributions with respect to arbitrary unknown distributions, and weak learning with membership queries with respect to the uniform distribution.Our framework is based on the theory of Solomonoff’s inductive inference and the universal extrapolation algorithm of Impagliazzo and Levin (FOCS’90). Conceptually, the framework demonstrates that Pessiland is, in fact, a wonderland for machine learning in which various learning tasks can be efficiently solved by the generic algorithm of universal extrapolation.

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.

Which concepts can we learn efficiently on average? In this paper, we investigate the capability of a natural average-case learning framework, heuristic PAC (heurPAC) learning to answer this and some other related questions. Roughly speaking, we say that a concept class is heurPAC learnable if there exists a learning algorithm that given $n, s\in\mathbb{N}$ and $\epsilon,\delta,\eta\in(0,1]$ as input, learns all but $\eta$ fraction of $n$-input target functions represented as $s$-bit strings in the class from passively collected examples and then outputs an $\epsilon$-close hypothesis with failure probability at most $\delta$ in polynomial-time in $n$, $s$, $\epsilon^{-1},\delta^{-1}$, and $\eta^{-1}$, where each example is generated according to some example distribution. First, we establish a positive learnability result. Specifically, we show that a simple Fourier-based algorithm heurPAC learns $\Omega(\log n)$-junta functions on the uniform distribution, which is a central open question in the original PAC learning model. Our technical contribution is to introduce the notion of elusive functions that captures hard-to-learn cases and to establish a polynomial relation between the running time and the fraction of such elusive functions. Second, we present clear relations between heurPAC learnability and cryptography. Particularly, we show that for any efficiently evaluated class $\mathscr{C}$, (1) if $\mathscr{C}$ is not heurPAC learnable, then an auxiliary-input one-way function (AIOWF) exists; (2) if $\mathscr{C}$ is not heurPAC learnable on the uniform distribution, then an infinitely-often one-way function (io-OWF) exists. As a corollary, we also present new characterizations for AIOWF and io-OWF based on heurPAC learnability, which is conceptually stronger than the previous ones that are based on average-case learnability for fixed parameters. These results show that our framework might yield heuristic learners with theoretical guarantees for broader classes than the usual PAC learning framework, and any efficiently evaluated class has a potential for such a heuristic learner or a secure cryptographic primitive. Through this paper, we suggest further research toward the win-win “learning vs. cryptography” paradigm.

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption might be sufficient for worst-case learning than the feasibility of worst-case algorithms for NP problems. In this study, we investigate whether these worst-case re-quirements for learning are satisfied on the basis of only average-case assumptions in order to understand the nature of learning. First, we construct a strong worst-case learner based on the assumption that DistNP ⊆ AvgP, i.e., in Heuristica. Our learner agnostically learns all polynomial-size circuits on all unknown P/ poly-samplable distributions in polynomial time, where the complexity of learning depends on the complexity of sampling examples. Second, we study the limitation of relativizing constructions of learners based on average-case heuristic algorithms. Specifically, we construct a powerful oracle such that DistPH ⊆ AvgP, i.e., every problem in PH is easy on average, whereas UP ∩ coUP and PAC learning on almost-uniform distributions are hard even for 2n/w(1og n)- time algorithms in the relativized world, which improves the oracle separation presented by Impagliazzo (CCC 2011). The core concept of our improvements is the consideration of a switching lemma on a large alphabet, which may be of independent interest. The lower bound on the time complexity is nearly optimal because Hirahara (STOC 2021) showed that DistPH ⊆ AvgP implies that PH can be solved in time 2O(n/ log n)under any relativized world. The full version of this paper is available on ECCC [1].

Constructing one-way functions based on NP-hardness is a central challenge in theoretical computer science. Unfortunately, Akavia et al. [Akavia et al., 2006] presented strong evidence that a nonadaptive black-box (BB) reduction is insufficient to solve this challenge. However, should we give up such a central proof technique even for an intermediate step? In this paper, we turn our eyes from standard cryptographic primitives to weaker cryptographic primitives allowed to take auxiliary-input and continue to explore the capability of nonadaptive BB reductions to base auxiliary-input primitives on NP-hardness. Specifically, we prove the followings: - if we base an auxiliary-input pseudorandom generator (AIPRG) on NP-hardness via a nonadaptive BB reduction, then the polynomial hierarchy collapses; - if we base an auxiliary-input one-way function (AIOWF) or auxiliary-input hitting set generator (AIHSG) on NP-hardness via a nonadaptive BB reduction, then an (i.o.-)one-way function also exists based on NP-hardness (via an adaptive BB reduction). These theorems extend our knowledge on nonadaptive BB reductions out of the current worst-to-average framework. The first result provides new evidence that nonadaptive BB reductions are insufficient to base AIPRG on NP-hardness. The second result also yields a weaker but still surprising consequence of nonadaptive BB reductions, i.e., a one-way function based on NP-hardness. In fact, the second result is interpreted in the following two opposite ways. Pessimistically, it shows that basing AIOWF or AIHSG on NP-hardness via nonadaptive BB reductions is harder than constructing a one-way function based on NP-hardness, which can be regarded as a negative result. Note that AIHSG is a weak primitive implied even by the hardness of learning; thus, this pessimistic view provides conceptually stronger limitations than the currently known limitations on nonadaptive BB reductions. Optimistically, it offers a new hope: breakthrough construction of auxiliary-input primitives might also provide construction standard cryptographic primitives. This optimistic view enhances the significance of further investigation on constructing auxiliary-input or other intermediate cryptographic primitives instead of standard cryptographic primitives.

We consider the problem of enumerating relevant features hidden in other irrelevant information for multi-labeled data, which is formalized as learning juntas. A $k$-junta function is a function which depends on only $k$ coordinates of the input. For relatively small $k$ w.r.t. the input size $n$, learning $k$-junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. In real-world, however, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field $\mathbb{F}_q$, and give, roughly speaking, an $O(n^{0.8k})$-time learning algorithm for $k$-juntas over $\mathbb{F}_q$. Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where $q=3$ and we give an affirmative answer to the question posed by Mossel et al. (2004).

We investigate the meaning of efficient learnability from several different perspectives. The purpose is to give new insights into central problems in computational learning theory (CoLT). Specifically, we discuss the following two questions related to efficient PAC learnability. First, we investigate the gap between PAC learnability for polynomial-size circuits and weak cryptographic primitives taking auxiliary-input. Applebaum et al. observed that such a weak primitive is enough to show the hardness of PAC learning. However, the opposite direction is still unknown. In this paper, we introduce the following two notions: (1) a variant model of PAC learning whose hardness corresponds to auxiliary-input one-way functions; (2) a variant of a hitting set generator corresponding to the hardness of PAC learning. The equivalence gives a clearer insight into the gap between the hardness of learning and weak cryptographic primitives. Second, we discuss why proving efficient learnability is difficult. This question is natural because few classes are known to be polynomially learnable at present. In this paper, we formulate a task of determining efficient learnability as a meta-PAC learning problem and show that our meta-PAC learning is exactly as hard as PAC learning. Our result insists on one possibility: a hard-to-learn instance itself yields the hardness of proving efficient learnability. Our technical contribution is to give (1) a general framework for translating the hardness of PAC learning into auxiliary-input primitives, and (2) a new formulation to discuss the hardness of determining efficient learnability. Our work yields new important frontiers related to CoLT, including investigation of the learning hierarchy.