UC Berkeley

The nascent field of Fine-Grained Complexity Theory has emerged and grown rapidly in the past decade. By studying ``Hardness within P'' and the connections of problems computable in, say, $n^{2}$ time versus $n^{3}$ time, this field addresses the practical efficiency of problems. However, while this more deeply quantitative approach better addresses practical hardness problem-by-problem, we lose connection to key qualitative claims of classical complexity theory such as the general ability to hide secrets (Cryptography), the ability to show that a world where we have access to randomness is no more powerful computationally than a deterministic one (Derandomization), and the ability to take a problem that is hard in the worst-case scenario and turn it into one that is hard almost always (Hardness Amplification).

We show that these connections can be recovered and that the problem-specific claims of Fine-Grained Complexity Theory cannot exist in a vacuum without ramifications to classical structural Complexity Theory. Namely, we show that the core worst-case hardness assumptions that define Fine-Grained Complexity Theory yield:

Hardness Amplification: We attain Fine-Grained problems that are hard on average (Ball et al., STOC '17). By achieving average-case hardness within the Fine-Grained world, we use this as a stepping stone to achieve both Cryptographic primitives and Derandomization.

Cryptography: We obtain the first Proofs of Work (PoWs) from worst-case complexity assumptions, thus finally placing these fundamental primitives on a rigorous theoretical foundation (Ball et al., CRYPTO '18). We further propose the concept of Fine-Grained Cryptography and this call has now been answered in (LaVigne et al., CRYPTO '20) where some progress is made towards achieving Public-Key Fine-Grained Cryptography.

Derandomization: We construct complexity-theoretic Pseudorandom Generators (Carmosino et al., ICALP '18). This both achieves the best known derandomizations from uniform assumptions as well as connects the problem-centric Fine-Grained Complexity to the resource-centric study in Complexity Theory of randomness as a resource.