A Sharp Characterization of Pessiland

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.